Description
Input
* 第1行: 两个由空格隔开的整数: N和V * 第2到第N+1行: 第i+1行表示第i种游戏平台的价格和可以在这种游戏平台上面运行的游 戏。包含: P_i, G_i还有G_i对由空格隔开的整数GP_j, PV_j
Output
* 第1行: 农夫约翰在预算内可以得到的最大的产出值。
Sample Input
3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60
Sample Output
210
HINT
Source
Gold
背包~
有依赖的背包，虽然看起来好麻烦但是数据范围小得夸张……所以我们可以用f[i][j]表示选到第i个组，已花费j的代价所能获得的最大收益，i维可以滚动。
我们在每次DP前先将选该组的代价减去，再进行普通的背包DP就好了~
#include<cstdio>
#include<iostream>
using namespace std;int n,m,f[2][100001],kkz,ans;struct node{int val,cost;
}p[51],a[51][11];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int main()
{n=read();m=read();for(int i=1;i<=n;i++){p[i].cost=read();p[i].val=read();for(int j=1;j<=p[i].val;j++) a[i][j].cost=read(),a[i][j].val=read();}for(int i=1;i<=n;i++){kkz^=1;for(int j=0;j<p[i].cost;j++) f[kkz][j]=f[kkz^1][j];for(int j=p[i].cost;j<=m;j++) f[kkz][j]=f[kkz^1][j-p[i].cost];for(int j=1;j<=p[i].val;j++)for(int k=m-a[i][j].cost;k>=p[i].cost;k--) f[kkz][k+a[i][j].cost]=max(f[kkz][k+a[i][j].cost],f[kkz][k]+a[i][j].val);for(int k=p[i].cost;k<=m;k++) f[kkz][k]=max(f[kkz][k],f[kkz^1][k]),ans=max(ans,f[kkz][k]);}printf("%d\n",ans);return 0;
}