题解：P2967 [USACO09DEC] Video Game Troubles G

· · 题解

题目传送门

思路

本题和P1064这道题十分相似，但如果按照对每组物品可能的购买策略打包，由于每款主机最多有 10 款游戏，那么每组最多打包 2^{10}=1024 件新物品，时间复杂度为 O(n \cdot V \cdot 1024)，会超时。

本题的另一种思路是：仍将每个主机及其游戏看作一个组，按已处理的主机数经行阶段划分，设阶段变量 i 代表已处理前 i 台主机，设 f_{i,j} 代表从前 i 台主机中恰好花费 j 元购买游戏得到的最大奶量（j 元必须用完）。当问题进入第 i 阶段时，分两步进行。

第一步：先忽略第 i 台主机的价格，只对第 i 台主机的 G_i 款游戏做 01 背包，此时得到的 f_{i,j} 为从前 i 台主机中花费 j 元购买游戏得到的伪收益（若购买第 i 台主机的游戏，还没有算买第 i 台主机花的钱）。

第二步：再考虑第 i 台主机的价格，计算第 i 阶段的真实收益 f1_{i,j}。对于第 i 阶段，要么不买第 i 台主机及其游戏，此时 f1_{i,j}=f_{i-1,j}；要么购买第 i 台主机的若干款游戏，而购买第 i 台主机的若干款游戏的最优收益记录在 f_{i,j} 里，但由于 f_{i,j} 的计算忽略了主机的价格，因此计算真实收益时要把主机价格减去，此时 f1_{i,j}=f_{i,j-P_i}。

在第 i 阶段开始前，复制 f_{i,j} 的值为 f1_{i-1,j} 的值，即 f_{i,j} 的初始值为第 i-1 阶段花费 j 元的最大产奶量（真实收益）；然后只对第 i 台主机的 G_i 款游戏做 01 背包计算第 i 阶段花费 j 元的最大产奶量 f_{i,j}（伪收益）；最后计算第 i 阶段花费 j 元的最大产奶量 f1_{i,j}（真实收益）。

代码

#include<bits/stdc++.h>
using namespace std;
int P[55],num[55];//主机价格，包含的游戏数量
int p[55][15],v[55][15];//第i台主机第j款游戏的价格，价值
int f[55][100001],f1[55][100001];
//f[i][j]代表从前i台主机中恰好花费j元购买游戏得到的最大产奶量(伪收益)
//f1[i][j]代表从前i台主机中恰好花费j元购买游戏得到的最大产奶量(真实收益)
int main(){
    int n,V;//游戏主机种数，预算
    int s=0;
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>P[i]>>num[i];
        for(int j=1;j<=num[i];j++){
            cin>>p[i][j]>>v[i][j];
        }
    }
    memset(f,0xcf,sizeof(f));
    f1[0][0]=0;
    for(int i=1;i<=n;i++){
        //第i阶段开始,复制f1[i-1][k]至f[i][k]中
        for(int k=0;k<=V;k++)
        f[i][k]=f1[i-1][k];
        //计算第i阶段的伪收益f[i][k]
        for(int j=1;j<=num[i];j++){
            for(int k=V;k>=0;k--){
                if(k>=p[i][j])
                    f[i][k]=max(f[i][k],f[i][k-p[i][j]]+v[i][j]);
            }
        }
        //计算第i阶段的真实收益f1[i][k]
        for(int k=0;k<=V;k++){
            //不选第i台主机
            f1[i][k]=f1[i-1][k];
            //选第i台主机
            if(k>=P[i])f1[i][k]=max(f1[i][k],f[i][k-P[i]]);
        }
    }
    int ans=-1e9;
    for(int j=0;j<=V;j++)ans=max(ans,f1[n][j]);
    cout<<ans;
    return 0;
}