三天了,从一点不会单调队列到AC。。。。。
dp[i]表示i容量是否能凑出来
num[i]表示当前i容量使用当前硬币的数目
关于单调队列优化多重背包的思想,在《国家集训队2009论文集浅谈几类背包题》有详细介绍
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int a[110]; int c[110]; bool dp[100010]; int num[100010]; int main() { int n,m; while(scanf("%d%d",&n,&m),n||m) { for(int i=0;i<n;i++) { scanf("%d",a+i); } for(int i=0;i<n;i++) { scanf("%d",c+i); } for(int i=0;i<=m;i++) { dp[i]=false; } dp[0]=true; for(int i=0;i<n;i++) { for(int j=0;j<=m;j++) { num[j]=0; } for(int j=a[i];j<=m;j++) { if(dp[j-a[i]]&&!dp[j]&&num[j-a[i]]<c[i]) { num[j]=num[j-a[i]]+1; dp[j]=true; } } } int ant=0; for(int i=1;i<=m;i++) { if(dp[i]) { ant++; } } printf("%d\n",ant); } return 0; }