邱老师玩游戏
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);
}
}