题解 P3423 【[POI2005]BAN-Bank Notes】

· · 题解

看到这一道题其实很容易就看出了第一问的做法就是多重背包，然后第二问要求输出方案，那么我们很容易就会想到DP要输出方案，很简单的一个方法就是保存当前的状态从哪里转移过来的，然后倒着输出就可以了，就做一个数组d，来保存怎么转移的，很多的dp输出方案都可以用类似的方法输出，不知道的同学可以试一下。

其中d[i][j]表示状态为f[i][j]时，是由f[i-1][d[i][j]]转移过来的
void print(int x,int y){
    if(!x)return;
    print(x-1,d[x][y]);
    printf("%d ",(y-d[x][y])/w[x]);
}

普通的直接多重背包对于这一道题明显会超时，所以我们应该使用优化算法。多重背包一共两种优化（我所知道的），二进制优化和单调队列优化。一般来说用二进制优化是比单调队列快一点的，因为单调队列常数比较大，但如果用二进制优化的话个人感觉不怎么方便统计如何转移过来的，所以我在这一题选择了单调队列优化，使用单调队列优化的话统计如何转移就可以非常简单做出来了。如果你不懂如何单调队列优化我推荐一篇博客，个人感觉讲得不错。

https://blog.csdn.net/sinat_34943123/article/details/52857327

这是我昨天晚上看到这题，当场学单调队列优化真正把我看懂的一篇博客。也感谢这一位dalao的博客，没有这篇博客我肯定过不了这题

代码如下

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
#include<deque>
#include<set>
#include<map>
#define N 20005
using namespace std;
struct Node{
    int x,y;
}q1[N],q2[N];
int n,m,w[N],c[N],f[N],d[205][N];
int head1,head2,tail1,tail2;
void print(int x,int y){//打印方案 
    if(!x)return;
    print(x-1,d[x][y]);
    printf("%d ",(y-d[x][y])/w[x]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)   
        scanf("%d",&c[i]);
    scanf("%d",&m);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){//单调队列优化背包 
        for(int j=0;j<w[i];j++){
            head1=head2=1;
            tail1=tail2=0;
            for(int k=j,cnt=0;k<=m;cnt++,k+=w[i]){
                int xx=k/w[i];
                if(tail1-head1==c[i]){
                    if(q1[head1].x==q2[head2].x)
                        head2++;
                    head1++;
                }
                int t=f[k]-cnt;
                q1[++tail1].x=t,q1[tail1].y=k;
                while(head2<=tail2&&t<q2[tail2].x)
                    tail2--;
                q2[++tail2].x=t,q2[tail2].y=k;
                f[k]=q2[head2].x+cnt;
                d[i][k]=q2[head2].y;
            }
        }
    }
    printf("%d\n",f[m]);
    print(n,m);
    return 0;
}

PS：

1.本来我想用单调队列后，想直接看题解怎么做的单调队列，以此来学习，但题解里只有二进制优化的做法，我又没怎么看懂，就自己学，学了写这篇题解帮助一下和我一样的同学。

2.个人认为讲得比较清楚，但是平常不管是文化课还是竞赛给别人讲题基本别人听不懂。若有不懂可以私聊，我尽量回复。

3.祝NOIP2018 RP++