UESTC_邱老师玩游戏 2015 UESTC Training for Dynamic Programming<Problem G>

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

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

解题思路:

首先我们构造一个虚拟结点 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 ;

}