首页 > 代码库 > 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(多重背包+单调队列优化)