在discuss里看到的这个方法,不需要二进制优化,也不需要单调队列优化,仅需增加一个数组记录每个coin使用的个数,既好写有好理解,话说那个高端大气的单调队列优化各种复杂抽象难以理解,膜拜ing。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m; int a[105],c[105],used[100010]; bool f[100010]; int i,j; int main(){ while(scanf("%d%d",&n,&m)){ if(n==0&&m==0) break; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) scanf("%d",&c[i]); memset(f,0,sizeof(f)); f[0]=1; int ans=0; for(i=1;i<=n;i++){ memset(used,0,sizeof(used)); for(j=a[i];j<=m;j++) if(!f[j]&&f[j-a[i]]&&used[j-a[i]]<c[i]){ f[j]=1; used[j]=used[j-a[i]]+1; ++ans; } } printf("%d\n",ans); } return 0; }