【jzoj1593】【DP】【GDKOI训练】电视游戏问题

DP】【GDKOI训练】电视游戏问题"/>

【jzoj1593】【DP】【GDKOI训练】电视游戏问题

题目描述

农夫约翰的奶牛们游戏成瘾！本来FJ是想要按照陶教授的做法拿她们去电击戒瘾的，可是后来他发现奶牛们玩游戏之后比原先产更多的奶。很明显，这是因为满足的牛会产更多的奶。但是，奶牛们在哪个才是最好的游戏平台这个问题上产生了巨大的分歧。一只奶牛想要买一台Xbox 360来跑《光晕3》；另外一只奶牛想要一台任天堂Wii来跑《任天堂明星大乱斗X》；第三只奶牛想要在PlayStation 3上面玩《潜龙谍影4》，顺便还能看某些高画质的电影。

FJ想要在给定的预算内购入一些游戏平台和一些游戏，使他的奶牛们生产最多的奶牛以养育最多的孩子。FJ研究了N（1 <= N <= 50）种游戏平台，每一种游戏平台的价格是P_i（1 <= P_i <= 1000），并且每一种游戏平台有G_i（1 <= G_i <= 10）个只能在这种平台上运行的游戏。很明显，奶牛必须先买进一种游戏平台，才能买进在这种游戏平台上运行的游戏。每一个游戏有一个游戏的价格GP_j（1 <= GP_j 价格 <= 100）并且有一个产出值PV_j（1 <= PV_j<= 1000000），表示一只牛在玩这个游戏之后会产出多少牛奶。

最后，农夫约翰的预算为V（1 <= V <= 100000），即他最多可以花费的金钱。请帮助他确定应该买什么游戏平台和游戏，使得他能够获得的产出值的和最大。

考虑下面的数据，有N种游戏平台，并且有V=$800预算。第一种游戏平台花费$300并且有两个游戏，价格分别为$30和$25，它们的产出值如下所示:

游戏 #    花费      产出值1          $30       502          $25       80

第二种平台价格为$600，并且只有一种游戏:

游戏 #    花费      产出值1          $50       130

第三种平台价格为$400，并且有三种游戏:

游戏 #    花费      产出值1         $40        702         $30        403         $35        60

农夫约翰应该买第1和第3种平台，并且买平台1的游戏2，还有平台3的游戏1和游戏3。使得最后他最后的产出值最大，为210产出值:

    预算:        $800     平台 1      -$300游戏 2  -$25               80平台 3      -$400游戏 1   -$40              70游戏 3   -$35              60-------------------------------------------总计:           0 (>= 0)      210

输入
第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

解题思路

01背包的变形
设 D P [ i ] DP[i] DP[i]表示最优值

• 在普通的背包转移之前，先把背包转移到花费平台钱的情况
• 在普通转移时，容量是游戏的花费+平台花费

但是会有一个问题，这是一定选这个平台游戏的情况，但是如果不选才是最优值呢？

设 D P t [ i ] DPt[i] DPt[i]表示选当前平台的游戏的最优值
D P f [ i ] DPf[i] DPf[i]表示不选当前平台游戏的最优值

• 每做一个平台就要把前一个平台的最优值转移过来

#include<iostream>
#include<cstdio>
using namespace std;
struct DT{int vn,n;int w[20],v[20];
}f[100];
int n,m,DPt[100100],DPf[100100];
int main(){freopen("vidgame.in","r",stdin);freopen("vidgame.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&f[i].vn,&f[i].n);for(int j=0;j<=m;j++){DPf[j]=max(DPf[j],DPt[j]);//把上一个平台的最优值转移过来if(j>=f[i].vn)DPt[j]=max(DPf[j-f[i].vn],DPt[j-f[i].vn]);//从花费平台钱数的地方转移过来}for(int j=1;j<=f[i].n;j++){scanf("%d%d",&f[i].w[j],&f[i].v[j]);for(int k=m;k>=f[i].vn+f[i].w[j];k--)//最低值从平台数+游戏数转移过来DPt[k]=max(DPt[k],DPt[k-f[i].w[j]]+f[i].v[j]);}}printf("%d",max(DPt[m],DPf[m]));//最后也要去个max
}