bzoj 1531 Bank notes 多重背包/单调队列

时间：2023-12-30 20:15:32

多重背包二进制优化终于写了一次，注意j的边界条件啊，疯狂RE(还是自己太菜了啊啊)最辣的辣鸡

#include<bits/stdc++.h>

using namespace std;

int n,sum;

const int N=;

const int C=;

const int K=;

const int inf=0x3f3f3f3f;

int w[N*C],idx,num[N*C];

int b[N],c[N];

//面值  个数 

int f[K],k;

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&b[i]);

    for(int i=;i<=n;i++) scanf("%d",&c[i]);

    scanf("%d",&k);

    idx=;

    for(int i=;i<=n;i++){

        for(int j=;j<=c[i];j<<=){

            w[++idx]=b[i]*j;

            num[idx]=j;

            c[i]-=j;

        }

        if(c[i]>){

            w[++idx]=b[i]*c[i];

            num[idx]=c[i];

        }

    }

    memset(f,inf,sizeof f);

    f[]=;

    for(int i=;i<=idx;i++)

    for(int j=k;j>=w[i];j--)

    f[j]=min(f[j],f[j-w[i]]+num[i]);

    printf("%d",f[k]);return ;

}

2.单调队列写法以后再写吧，真是没有看懂

相关文章