题目描述

输入

* 第1行: 两个由空格隔开的整数: N和V * 第2到第N+1行: 第i+1行表示第i种游戏平台的价格和可以在这种游戏平台上面运行的游 戏。包含: P_i, G_i还有G_i对由空格隔开的整数GP_j, PV_j

输出

* 第1行: 农夫约翰在预算内可以得到的最大的产出值。

样例输入

3 800

300 2 30 50 25 80

600 1 50 130

400 3 40 70 30 40 35 60

样例输出

210

---

题解

背包型dp

f[i][j]表示前i种平台中第i种不选，用j元的最大产出值，

g[i][j]表示前i种平台中第i中选，用j元的最大产出值。

那么就可以先给f[i][...]、g[i][...]赋初值（根据是否购买平台并由前一种平台决定值），然后所求问题就转化为01背包。

最后的答案是max(f[n][m],g[n][m])。

注意数组要赋极小值，以便在购买平台是只保留有效状态。

#include 
     
      #include 
      
       #include 
       
        using namespace std;int f[51][100001] , g[51][100001];int main(){    int n , m , i , j , p , c , v , w;    scanf("%d%d" , &n , &m);    memset(f , 0x80 , sizeof(f));    memset(g , 0x80 , sizeof(g));    for(i = 0 ; i <= m ; i ++ )        f[0][i] = g[0][i] = 0;    for(i = 1 ; i <= n ; i ++ )    {        scanf("%d%d" , &p , &c);        for(j = 0 ; j <= m ; j ++ )        {            f[i][j] = max(f[i - 1][j] , g[i - 1][j]);            if(j >= p)                g[i][j] = max(f[i - 1][j - p] , g[i - 1][j - p]);        }        while(c -- )        {            scanf("%d%d" , &v , &w);            for(j = m ; j >= v ; j -- )                g[i][j] = max(g[i][j] , g[i][j - v] + w);        }    }    printf("%d\n" , max(f[n][m] , g[n][m]));    return 0;}