poj 3260双端队列优化多重背包+完全背包

#include<cstdio> #include<cstring> #define MAX(x,y) ((x)>(y)?(x):(y)) #define MIN(x,y) ((x)>(y)?(y):(x)) #define MAX_N 100200 using namespace std; int dp1[MAX_N],dp2[MAX_N]; int n,m,num; int c[MAX_N],v[MAX_N]; void solve() { memset(dp2,0x3f,sizeof(dp2)); dp2[0]=0; for(int i=0;i<n;i++) { for(int j=v[i];j<=m+num;j++) { dp2[j]=MIN(dp2[j],dp2[j-v[i]]+1); } } } void solve1() { int deqv[100000],deq[100000]; memset(dp1,0x3f,sizeof(dp1)); dp1[0]=0; for(int i=0;i<n;i++) { for(int a=0;a<v[i];a++) { int s=0,t=0; for(int j=0;j*v[i]+a<=m+num;j++) { int val=dp1[j*v[i]+a]-j; while(s<t&&deqv[t-1]>=val) t--; deq[t]=j; deqv[t++]=val; dp1[j*v[i]+a]=deqv[s]+j; if(deq[s]==j-c[i]) s++; } } } } int main() { scanf("%d%d",&n,&m); num=0; for(int i=0;i<n;i++) { scanf("%d",&v[i]); num=MAX(num,v[i]); } num*=num; for(int i=0;i<n;i++) scanf("%d",&c[i]); solve1(); solve(); int res=0x3f3f3f3f; for(int i=num+m;i>=0;i--) { res=MIN(res,dp1[i+m]+dp2[i]); } if(res==0x3f3f3f3f) printf("-1\n"); else printf("%d\n",res); return 0; }