G - 邱老师玩游戏
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
邱老师最近在玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中邱老师允许攻克M个城堡并获得里面的宝物。
但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮邱老师算出要获得尽量多的宝物应该攻克哪M个城堡吗？
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 and output
| Sample Input | Sample Output |
|---|---|
3 2 |
5 |
解题思路:
首先我们构造一个虚拟结点 0 ，这样成功的把森林转换成了树.
我们考虑f(i,j,k) -> 点i,正在决策j个儿子(j + 1 - > max 已经决策完毕),还可以攻击k次的最大收益（根结点已经被攻击)
这样，对于点i的每个儿子，枚举它的攻击次数进行转移<采用记忆化搜索>，转移方程不再累述.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector> using namespace std;
const int maxn = + ;
/*
f(i,j,k) -> 点i,正在决策j个儿子(j + 1 - > max 已经决策完毕),还可以攻击k次的最大收益（根结点已经被攻击)
*/
int n,m,f[maxn][maxn][maxn],value[maxn];
vector<int>E[maxn]; int dp(int i,int j,int k)
{
if (f[i][j][k] != -)
return f[i][j][k];
int & ans = f[i][j][k] = ;
if (j == E[i].size() || k == )
return ans = ;
// 正在考虑第 j 个儿子的攻击次数分配
ans = dp(i,j+,k); //不攻击
for(int v = ; v <= k ; ++ v)
ans = max(ans,dp(i,j+,k-v) + dp(E[i][j] , , v - ) + value[E[i][j]] ) ; //分配攻击次数
return ans;
} int main(int argc,char *argv[])
{
while(scanf("%d%d",&n,&m) && n)
{
memset(f,-,sizeof(f));
for(int i = ; i <= n ; ++ i)
{
int a;
scanf("%d%d",&a,&value[i]);
E[a].push_back(i);
}
printf("%d\n",dp(,,m));
for(int i = ; i <= n ; ++ i)
E[i].clear();
}
return ;
}