http://acm.hdu.edu.cn/showproblem.php?pid=2844
#include"iostream" #include"algorithm" using namespace std; int A[100010]; int C[100010]; int n; int m; int F[100010]; int main() { while(1) { cin>>n>>m; if(n==0&&m==0) { break; } for(int i=0;i<n;i++) { cin>>A[i]; } for(int i=0;i<n;i++) { cin>>C[i]; } memset(F,0,sizeof(F)); for(int i=0;i<n;i++) { if((C[i]*A[i])>=m) { for(int j=A[i];j<=m;j++) { F[j]=max(F[j-A[i]]+A[i],F[j]); } } else { int cnt=0; int now=1; while(1) { if((cnt+now)<=C[i]) { cnt=cnt+now; for(int j=m;j>=now*A[i];j--) { F[j]=max(F[j-now*A[i]]+now*A[i],F[j]); } now=now*2; } else { now=C[i]-cnt; for(int j=m;j>=now*A[i];j--) { F[j]=max(F[j-now*A[i]]+now*A[i],F[j]); } break; } } } } int sum=0; for(int i=1;i<=m;i++) { if(F[i]==i) sum++; } cout<<sum<<endl; } system("pause"); return 0; }