攻克城堡

城堡"/>

攻克城堡

【问题描述】 

小A很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中小A允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮小A算出要获得尽量多的宝物应该攻克哪M个城堡吗？

【输入描述】

每个测试样例首先包括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时输入结束。

【输出描述】

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

【输入样例】

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

【输出样例】

5

13

源代码：#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> List[201];
int m,n,DP[201][201],Value[201];
void DFS(int T,int M) //M代表此时还剩多少可攻击次数。
{int Length=List[T].size();DP[T][1]=Value[T]; //攻击该节点能够得到的财富值。for (int a=0;a<Length;a++) //继续攻击该节点下的子节点。
    {if (M>1)DFS(List[T][a],M-1);for (int b=M;b>=1;b--) //孩子节点攻击的次数。
        {int t=b+1;for (int c=1;c<t;c++) //从孩子节点中找攻击b次的最优值。DP[T][t]=max(DP[T][t],DP[T][t-c]+DP[List[T][a]][c]);}}
}
int main() //树形DP+01背包。
{while (scanf("%d%d",&n,&m)&&n||m) //持续读入。
    {memset(DP,0,sizeof(DP));memset(Value,0,sizeof(Value));for (int a=0;a<=n;a++)List[a].clear(); //预处理。for (int a=1;a<=n;a++){int Start;scanf("%d%d",&Start,&Value[a]);List[Start].push_back(a); //List[i]存储的是要想攻克i需要先攻克哪些节点。
        }DFS(0,m+1);printf("%d\n",DP[0][m+1]);}return 0;
}

转载于:.html