[POI2005]BAN-Bank Notes

BZOJ(不用输出方案)

洛咕(还要输出方案)

题意:BBB拥有一套先进的货币系统,这个系统一共有n种面值的硬币,面值分别为\(b_1,b_2,...,b_n\).但是每种硬币有数量限制,现在我们想要凑出面值m,求最少要用多少个硬币.

分析:对于第一问,多重背包的模型,用二进制拆分优化或者单调队列优化.我刚学了二进制优化，所以就来练练手，个人觉得这篇博客上的模板很好理解．

二进制拆分完后,就直接跑01背包模板了.设\(f[j]\)表示凑出面值\(j\)的最少所用硬币数.初始化\(f[0]=0\),其余赋为无穷大.目标\(f[m]\).

for(int i=1;i<=tot;i++)//tot:拆分后的新硬币总数
    for(int j=m;j>=val[i];j--)//val[i]:拆分后的第i个新硬币的面值
        f[j]=min(f[j],f[j-val[i]]+c[i])//c[i]:第i枚新硬币实际上组成的硬币数
        

重点是第二问很恶心.但是动态规划输出方案都有个套路,就是额外开一个数组,每次转移时记录一下从哪里转移来的,最后递归输出方案.

运用到本题中,就是我们开一个\(bool\)数组(题目卡空间,用\(int\)数组就\(MLE\)了)\(to[i][j]=1\)表示从第i个新硬币转移到了j面值.

    int sum=f[m];//sum:最少需用货币数(第一问答案)
    while(sum){
        while(!to[tot][m])tot--;//找到是从哪个新硬币转移到当前面值m的
        m-=val[tot];//m转移到上一次的面值
        ans[val[tot]/c[tot]]+=c[tot];//因为一枚新硬币是由若干个面值相同的旧硬币组成,故val[tot]/c[tot]就是该旧硬币的面值
        sum-=c[tot];//sum转移到上一次面值所用的货币数
        tot--;
    }

本题中数组大小真的不容易写,小了的话要不就\(RE\),要不就\(WA\),大了又会\(MLE\)...

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
const int N=205;
const int M=20005;
int b[N],c[3005],val[3005],f[M],ans[M];
bool to[3005][M];
int main(){
    int n=read(),tot=0;
    for(int i=1;i<=n;i++)b[i]=read();
//二进制拆分模板
    for(int i=1;i<=n;i++){
        int C=read();
        for(int j=1;j<=C;j=j<<1){
            val[++tot]=j*b[i];
            c[tot]=j;
            C-=j;
        }
        if(C){
            val[++tot]=C*b[i];
            c[tot]=C;
        }
    }
//01背包模板:
    memset(f,0x3f,sizeof(f));f[0]=0;
    int m=read();
    for(int i=1;i<=tot;i++)
        for(int j=m;j>=val[i];j--)
            if(f[j]>f[j-val[i]]+c[i]){
                f[j]=f[j-val[i]]+c[i];
                to[i][j]=1;
            }
    printf("%d\n",f[m]);
//输出方案:
    int sum=f[m];
    while(sum){
        while(!to[tot][m])tot--;
        m-=val[tot];
        ans[val[tot]/c[tot]]+=c[tot];
        sum-=c[tot];
        tot--;
    }
    for(int i=1;i<=n;i++)printf("%d ",ans[b[i]]);puts("");
    return 0;
}

[POI2005]BAN-Bank Notes

原文：https://www.cnblogs.com/PPXppx/p/10996608.html