题解 P2967 【[USACO09DEC]视频游戏的麻烦Video Game Troubles】

· · 题解

魔鬼教练举行了一次连续三天的动规测试，这题是T2(一共31题）我再也不想打动规了（手动黄豆再见）

这题很明显是背包类动规，最容易想到的思路当然是像金明的预算方案一样做分组01背包，f[i]表示花费为i时奶牛的最大产出值。状态转移方程也很好推。然而，不用试也知道

\huge{TLE!}

经过观察我们可以很轻易地得到一个结论，每个游戏平台之间是互不影响的，那么我们就有了一个大胆的想法：可不可以把当前平台单独动规出来后与前面合并呢？所以就有了g数组，g[j]表示在已经买了当前平台i的前提下，在1~i平台共花费j元所能带来的最大产出,是个简单的01背包（我相信你们都会哒）。然后将g和f数组进行合并（f[j]=max(f[j],g[j])）。具体实现过程看代码。

#include<bits/stdc++.h>
 using namespace std;
 int i,j,k,n,v,p,gc,gp,pv;
 long long f[1000005],g[1000005];
 inline int read()
{
    int x=0,c; bool f=0;
    for(;(c=getchar())<'0'||c>'9';f|=c=='-');
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
    return f?-x:x;
}
 int main()
{
    n=read(); v=read();
    for(i=1;i<=n;i++)
    {
        p=read(); gc=read();
        for(j=p;j<=v;j++) g[j]=f[j-p];
        for(j=1;j<=gc;j++)
        {
            gp=read(); pv=read();
            for(k=v-gp;k>=p;k--) g[k+gp]=max(g[k+gp],g[k]+pv);
        }
        for(j=p;j<=v;j++) f[j]=max(g[j],f[j]);
    }
    printf("%d",f[v]);
    return 0;
}