动态规划,多重部分和问题,,数组得要重复利用,不然会MLE。。
#include<iostream> #include<stdlib.h> #include<string.h> using namespace std; int dp[100000+2]; int a[100+2]; int c[100+2]; int main() { int n,m; while(scanf("%d %d",&n,&m)&&(n+m)!=0) { for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>c[i]; memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=0;i<n;i++) { for(int j=0;j<=m;j++) { if(dp[j]>=0) dp[j]=c[i]; else if(j<a[i]||dp[j-a[i]]<=0) dp[j]=-1; else dp[j]=dp[j-a[i]]-1; } } int ans=0; for(int i=1;i<=m;i++) if(dp[i]>=0) ans++; cout<<ans<<endl; } }