BZOJ1775[USACO 2009 Dec Gold 3.Video Game Troubles]—

题目描述

输入

* 第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

一看到这题第一感觉就是背包，这题确实就是背包，只不过和平常的背包有些不同，在卖一些东西之前要先买另一个东西，而且这个东西还没有价值(虽然有没有价值不太重要qwq)。既然买游戏的前提是买游戏平台，那么我们不妨以是否买游戏平台做状态来转移，设f[i][j]代表不买第i个游戏平台总共花了j元的最大价值、g[i][j]代表买第i个游戏平台总共花了j元的最大价值。对于买了游戏平台的状态(也就是每个g[i][j])再对它包含的游戏进行状态转移。但要注意数组初始值要赋成极小值来避免无用状态的转移。

最后附上代码。

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m;

int x,y;

int v,c;

int g[51][100010];

int f[51][100010];

int main()

{

    scanf("%d%d",&n,&m);

    memset(g,0x80,sizeof(g));

    memset(f,0x80,sizeof(f));

    for(int i=0;i<=m;i++)

    {

        g[0][i]=f[0][i]=0;

    }

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

    {

        scanf("%d%d",&v,&c);

        for(int j=0;j<=m;j++)

        {

            f[i][j]=max(f[i-1][j],g[i-1][j]);

            if(v<=j)

            {

                g[i][j]=max(g[i-1][j-v],f[i-1][j-v]);

            }

        }

        while(c--)

        {

            scanf("%d%d",&x,&y);

            for(int j=m;j>=v;j--)

            {

                g[i][j]=max(g[i][j],g[i][j-x]+y);

            }

        }

    }

    printf("%d",max(f[n][m],g[n][m]));

}

巴特西

BZOJ1775[USACO 2009 Dec Gold 3.Video Game Troubles]——DP

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章