邱老师玩游戏

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/65

Description

邱老师最近在玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中邱老师允许攻克M个城堡并获得里面的宝物。

但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮邱老师算出要获得尽量多的宝物应该攻克哪M个城堡吗？

wij 千克的蛋糕，Gorwin从左上角(1,1)的格子开始走，走到右下角(n,m)的格子。在每一步中，Gorwin可以向右或者向下走，即是：Gorwin 站在(i,j)的时候，她可以走向(i+1,j)或者(i,j+1) (然而她不能走出这个花园)。当Gorwin到达一个格子的时候，她可以把那个格子里面的蛋糕吃完或者不吃。但是，她不能只吃一部分。她的胃不是那么大，所以她最多只能吃K千克的蛋糕。现在，Gorwin站在左上角，她在看蛋糕园的地图，想要找出一条路，能够使得她吃到的蛋糕最多的一条路。请你来帮帮忙。

Input

每个测试实例首先包括2个整数，N,M.(1 <= M <= N <= 200);

在接下来的N行里，每行包括2个整数，a,b.

在第 i 行，a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡，如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。

当N = 0, M = 0输入结束。

Output

对于每个测试实例，输出一个整数，代表邱老师攻克M个城堡所获得的最多宝物的数量。

Sample Input

3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0

Sample Output

5 13

HINT

题意

题解：

背包dp～

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

vector<int> e[];

struct node

{

    int x,y;

}a[];

int dp[][];

int dp2[];

int n,m;

void dfs(int u)

{

    dp[u][]=a[u].y;

    dp[u][]=;

    for(int i=;i<e[u].size();i++)

    {

        int v=e[u][i];

        dfs(v);

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

        {

            for(int k=;k<j;k++)

            {

                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);

            }

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n==&&m==)

            break;

        memset(dp,,sizeof(dp));

        memset(dp2,,sizeof(dp2));

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

            e[i].clear();

        memset(a,,sizeof(a));

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

        {

            scanf("%d%d",&a[i].x,&a[i].y);

            if(a[i].x!=)

                e[a[i].x].push_back(i);

        }

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

        {

            if(a[i].x==)

                dfs(i);

        }

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

        {

            if(a[i].x==)

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

                    for(int k=;k<=j;k++)

                    {

                        dp2[j]=max(dp2[j],dp2[j-k]+dp[i][k]);

                    }

        }

        int ans=dp2[m];

        /*

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

        {

            for(int j=1;j<300;j++)

                ans=max(ans,dp[i][j]);

        }

        */

        printf("%d\n",ans);

    }

}

邱老师

UESTC 2015dp专题 G 邱老师玩游戏 背包dp