[Luogu2967] 视频游戏的麻烦Video Game Troubles

农夫约翰的奶牛们游戏成瘾！本来约翰是想要按照调教兽的做法拿她们去电击戒瘾的，可是后来他发现奶牛们玩游戏之后比原先产更多的奶.很明显，这是因为满足的牛会产更多的奶.

但是，奶牛们在哪个才是最好的游戏平台这个问题上产生了巨大的分歧.约翰想要在给定的预算内购入一些游戏平台和一些游戏，使他的奶牛们生产最多的奶牛以养育最多的孩子.

约翰研究了N种游戏平台，每一种游戏平台的价格是Pi 并且每一种游戏平台有Gi个只能在这种平台上运行的游戏.很明显，奶牛必须先买进一种游戏平台，才能买进在这种游戏平台上运行的游戏.每一个游戏有一个游戏的价格GPi并且有一个产出值PVj< 1000000)，表示一只牛在玩这个游戏之后会产出多少牛奶.最后，农夫约翰的预算为V<100000)，即他最多可以花费的金钱.请帮助他确定应该买什么游戏平台和游戏，使得他能够获得的产出值的和最大.

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and V

* Lines 2..N+1: Line i+1 describes the price of and the games

available for console i; it contains: P_i, G_i, and G_i pairs of space-separated integers GP_j, PV_j

输出格式：

* Line 1: The maximum production value that Farmer John can get with his budget.

输入输出样例

输入样例#1：

3 800

300 2 30 50 25 80

600 1 50 130

400 3 40 70 30 40 35 60

输出样例#1：


第一次做这样的DP？(雾)
设f[i][j]表示考虑完前i个平台，花j元钱的最大收益。
然后每次强制选了第i个平台，然后对这个平台的物品进行一次o1背包，求出必须选第i个平台时花j元钱的最大收益。
然后再每次与上一次的DP结果比较一下，看看是否在花了j元钱的时候，选择第i个平台更优...
(雾)长见识了，DP还能这么玩。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <bitset>

#include <algorithm>

using namespace std;

#define reg register

#define gc getchar

inline int read() {

    int res=;char ch=gc();bool fu=;

    while(!isdigit(ch)){if(ch=='-')fu=;ch=gc();}

    while(isdigit(ch))res=(res<<)+(res<<)+(ch^), ch=gc();

    return fu?-res:res;

}

int n, m;

int f[][];

int main()

{

    n = read(), m = read();

    for (reg int i =  ; i <= n ; i ++)

    {

        int p = read(), g = read();

        for (reg int j = p ; j <= m ; j ++) f[i][j] = f[i - ][j - p];

        for (reg int k =  ; k <= g ; k ++)

        {

            int cost = read(), val = read();

            for (reg int j = m ; j >= cost + p ; j --) f[i][j] = max(f[i][j], f[i][j - cost] + val);

        }

        for (reg int j =  ; j <= m ; j ++) f[i][j] = max(f[i][j], f[i - ][j]);

    }

    cout << f[n][m] << endl;

    return ;

}

巴特西

[Luogu2967] 视频游戏的麻烦Video Game Troubles

输入输出格式

输入输出样例

最新文章

热门文章