专栏文章

题解：P2967 [USACO09DEC] Video Game Troubles G

DDiaoHantong
P2967题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqtzvlm
此快照首次捕获于
2025/12/04 10:43
3 个月前
此快照最后确认于
2025/12/04 10:43
3 个月前
查看原文

题目传送门

思路

本题和P1064P1064这道题十分相似，但如果按照对每组物品可能的购买策略打包，由于每款主机最多有 1010 款游戏，那么每组最多打包 210=10242^{10}=1024 件新物品，时间复杂度为 O(n⋅V⋅1024)O(n \cdot V \cdot 1024)，会超时。
本题的另一种思路是：仍将每个主机及其游戏看作一个组，按已处理的主机数经行阶段划分，设阶段变量 ii 代表已处理前 ii 台主机，设 fi,jf_{i,j} 代表从前 ii 台主机中恰好花费 jj 元购买游戏得到的最大奶量（jj 元必须用完）。当问题进入第 ii 阶段时，分两步进行。
第一步：先忽略第 ii 台主机的价格，只对第 ii 台主机的 GiG_i 款游戏做 0101 背包，此时得到的 fi,jf_{i,j} 为从前 ii 台主机中花费 jj 元购买游戏得到的伪收益（若购买第 ii 台主机的游戏，还没有算买第 ii 台主机花的钱）。
第二步：再考虑第 ii 台主机的价格，计算第 ii 阶段的真实收益 f1i,jf1_{i,j}。对于第 ii 阶段，要么不买第 ii 台主机及其游戏，此时 f1i,j=fi−1,jf1_{i,j}=f_{i-1,j}；要么购买第 ii 台主机的若干款游戏，而购买第 ii 台主机的若干款游戏的最优收益记录在 fi,jf_{i,j} 里，但由于 fi,jf_{i,j} 的计算忽略了主机的价格，因此计算真实收益时要把主机价格减去，此时 f1i,j=fi,j−Pif1_{i,j}=f_{i,j-P_i}。
在第 ii 阶段开始前，复制 fi,jf_{i,j} 的值为 f1i−1,jf1_{i-1,j} 的值，即 fi,jf_{i,j} 的初始值为第 i−1i-1 阶段花费 jj 元的最大产奶量（真实收益）；然后只对第 ii 台主机的 GiG_i 款游戏做 0101 背包计算第 ii 阶段花费 jj 元的最大产奶量 fi,jf_{i,j}（伪收益）；最后计算第 ii 阶段花费 jj 元的最大产奶量 f1i,jf1_{i,j}（真实收益）。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...