luogu P2967 [USACO09DEC] Video Game Troubles G

CSP RP++

这道题就是一个背包升级的板子，

我不会告诉你，这题我用了半个小时才做完

本题的思路是：

第一步：

先忽略第 $i$ 台主机的价格，只对第 $i$ 款游戏的 $G _ {i}$ 款游戏做01背包，此时得到的 $f[i][j]$ 为从前 $i$ 台主机中花费了 $j$ 元购买游戏得到的伪收益。

第二步：

再考虑第 $i$ 台主机的价格，计算第 $i$ 阶段的真实收益 $f1[i][j]$。对于第 $i$ 阶段，要么不买第 $i$ 台主机及其游戏，此时 $f1[i]=f[i-1] [j]$。要么购买第i台主机及其若干款游戏，那么此时 $f1[i] [j] =f1 [i] [j-p[i]]$。

话不多说，上代码。

#include <bits/stdc++.h>
using namespace std;
int p[60],x[60],pp[60][20],v[60][20],f[105][100001],f1[105][100001];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i]>>x[i];
        for(int j=1;j<=x[i];j++)
        {
            cin>>pp[i][j]>>v[i][j];
        }
    }
    memset(f,0xcf,sizeof(f));
    memset(f,0xcf,sizeof(f));
    f1[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int k=0;k<=m;k++)
        {
            f[i][k]=f1[i-1][k];
        }
        for(int j=1;j<=x[i];j++)
        {
            for(int k=m;k>=0;k--)
            {
                if(k>=pp[i][j])
                {
                    f[i][k]=max(f[i][k],f[i][k-pp[i][j]]+v[i][j]);
                }
            }
        }
        for(int k=0;k<=m;k++)
        {
            f1[i][k]=f1[i-1][k];
            if(k>=p[i])
            {
                f1[i][k]=max(f1[i][k],f[i][k-p[i]]);
            }
        }
    }
    int ans=-1e9;
    for(int i=0;i<=m;i++)
    {
        ans=max(ans,f1[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}