首页 > 代码库 > poj1742 Coins(多重背包+单调队列优化)
poj1742 Coins(多重背包+单调队列优化)
/*这题卡常数....二进制优化或者单调队列会被卡必须+上个特判才能过QAQ单调队列维护之前的钱数有几个能拼出来的循环的时候以钱数为步长如果队列超过c[i]就说明队头的不能再用了 拿出来时刻维护sum表示之前的+v[i]能凑出j来的有几种注意先进队在更新f */#include<iostream>#include<cstdio>#include<cstring>#define maxm 100010#define maxn 110using namespace std;int n,m,v[maxn],c[maxn],f[maxm],ans,q[maxm],head,tail,sum;int main(){ for(;;){ scanf("%d%d",&n,&m); if(n==0&&m==0)break;ans=0; for(int i=0;i<=m;i++)f[i]=0;f[0]=1; for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=n;i++)scanf("%d",&c[i]); for(int i=1;i<=n;i++){ if(v[i]*c[i]>=m){ for(int j=v[i];j<=m;j++) if(f[j-v[i]]&&f[j]==0){ ans++;f[j]=1; } continue; } for(int s=0;s<v[i];s++){ head=1,tail=0,sum=0; for(int j=s;j<=m;j+=v[i]){ if(tail-head+1>c[i]){ sum-=q[head];head++; } q[++tail]=f[j];sum+=f[j];//这里先进队 就是说保证这些队列的f都是上一匹物品更新来的 if(sum&&f[j]==0){ ans++;f[j]=1; } } } } printf("%d\n",ans); } return 0;}
poj1742 Coins(多重背包+单调队列优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。