题解 P6567 [NOI Online #3 入门组]买表

· · 题解

一道多重背包的 板子(?) 题

STEP 1 分析题意

题目条件

  1. 有 n 种货币，每种有 a_i 张且价值 k_i 元；

  2. 有 m 块手表，每块手表 t_i 元；

  3. 分别输出每块手表是否可以刚好买到。

答题思路

有经验的同学肯定而已看出来只是一道标准的多重背包问题（当然普通背包都不会的同学可以自行先去这里的题目的题解里补课），每一个价钱是否可以恰好达到都可以由该价钱减去未使用货币的面值演变而来，转移方程易得：

dp_j=dp_{j-l\times k_i}|dp_j

当然，初始化时 dp_0 一定为 1，因为它可以被无条件购买。

该部分代码如下：

for (int f=1;f<=m;f++){
    memset(dp,0,sizeof(dp);
    for (int i=1;i<=n;i++){
        for (int j=t[f];j>=0;j--){
            for (int l=0;l<=a[i]&&l*k[i]<=j;l++){
                dp[j]=dp[j-l*k[i]]|dp[j];
            }
        }
    }
    if (dp[f]==1) puts("Yes");
    else puts("No");         
}

但是这样就完了吗？？？四维啊！！！这个时间复杂度……我都懒得去计算了……

所以，怎么优化呢？

我们可以发现，对于每一种货币搭配，每一个价钱是否能够到达其实是固定不变的，也就是说，我们只要知道一个最大值，其实是可以只循环一次的！

代码如下：

for (int i=1;i<=n;i++){
    for (int j=maxn;j>=0;j--){//maxn为最大的钱数
        for (int l=0;l<=a[i]&&l*k[i]<=j;l++){
            if (dp[j]==1) break;
            if (dp[j-l*k[i]]==1) dp[j]=1;//小优化，只要它为1就可以直接跳出第三层循环；
        }
    }
}
for (int i=1;i<=m;i++){//m个询问依次处理
    if (dp[t[i]]==1) puts("Yes");
    else puts("No");
}

这是我考试的时候写的代码 （90分），（实际上数组开小了就50分）因为这是三维的，所以还是太慢了，我们要把它压缩成二维的！

代码如下：

for (int i=1;i<=n;i++){//can记录每个价钱是否可以凑到，dp记录每个物品在某个价钱已使用的次数
        memset(dp,0,sizeof(dp));
        for(int j=k[i];j<=maxn;j++){
            if(can[j]==0&&can[j-k[i]]==1&&dp[j-k[i]]<a[i]){//如果该价钱没有到过且该价钱的上一个状态到过并且还有使用次数
                can[j]=1,dp[j]=dp[j-k[i]]+1;//标记
            }
        }
    }

STEP 2 AC code

#include<bits/stdc++.h>//万能头
using namespace std;
int n,m,k[201],a[201],t[100001],dp[500001],maxn,can[500001];//如题，注意dp和can要开大，开大！！！
int read(){
    int w=0,f=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        c=getchar();
    }
    while (c<='9'&&c>='0'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w;
}//快读
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);//优化
    freopen("watch.in","r",stdin);
    freopen("watch.out","w",stdout);//考试必备，洛谷爆0神器
    n=read();m=read();
    for (int i=1;i<=n;i++){
        k[i]=read();a[i]=read();
    }//读入
    for (int i=1;i<=m;i++){
        t[i]=read();
        maxn=max(maxn,t[i]);//取最大值
    }
    can[0]=1;//初始化
    for (int i=1;i<=n;i++){
        memset(dp,0,sizeof(dp));
        for(int j=k[i];j<=maxn;j++){
            if(can[j]==0&&can[j-k[i]]==1&&dp[j-k[i]]<a[i]){
                can[j]=1,dp[j]=dp[j-k[i]]+1;
            }
        }
    }//如上所述
    for (int i=1;i<=m;i++){
        if (can[t[i]]==1) puts("Yes");
        else puts("No");
    }//输出
    return 0;//好习惯++
}

祝这次崩了的同学下次RP++，超常的同学下次RP依旧！