首页 > ACM题库 > HDU-杭电 > HDU 4616-Game-动态规划-[解题报告]HOJ
2015
09-17

HDU 4616-Game-动态规划-[解题报告]HOJ

Game

问题描述 :

  Nowadays, there are more and more challenge game on TV such as ‘Girls, Rush Ahead’. Now, you participate int a game like this. There are N rooms. The connection of rooms is like a tree. In other words, you can go to any other room by one and only one way. There is a gift prepared for you in Every room, and if you go the room, you can get this gift. However, there is also a trap in some rooms. After you get the gift, you may be trapped. After you go out a room, you can not go back to it any more. You can choose to start at any room ,and when you have no room to go or have been trapped for C times, game overs. Now you would like to know what is the maximum total value of gifts you can get.

输入:

  The first line contains an integer T, indicating the number of testcases.
  For each testcase, the first line contains one integer N(2 <= N <= 50000), the number rooms, and another integer C(1 <= C <= 3), the number of chances to be trapped. Each of the next N lines contains two integers, which are the value of gift in the room and whether have trap in this rooom. Rooms are numbered from 0 to N-1. Each of the next N-1 lines contains two integer A and B(0 <= A,B <= N-1), representing that room A and room B is connected.
  All gifts’ value are bigger than 0.

输出:

  The first line contains an integer T, indicating the number of testcases.
  For each testcase, the first line contains one integer N(2 <= N <= 50000), the number rooms, and another integer C(1 <= C <= 3), the number of chances to be trapped. Each of the next N lines contains two integers, which are the value of gift in the room and whether have trap in this rooom. Rooms are numbered from 0 to N-1. Each of the next N-1 lines contains two integer A and B(0 <= A,B <= N-1), representing that room A and room B is connected.
  All gifts’ value are bigger than 0.

样例输入:

2
3 1
23 0
12 0
123 1
0 2
2 1
3 2
23 0
12 0
123 1
0 2
2 1

样例输出:

146
158

/*
    dp[node][i][0]: node节点 在 消耗i陷阱时 并从该节点往下走(或者理解为还有能力往下走)的最大权值
    dp[node][i][1]: node节点 在 消耗i陷阱时 并从子节点往上走(到该节点或者理解为没有能力接着走了)的最大权值


*/

#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define ReadFile(str) freopen(str,"r",stdin);
#define CLR(c,v) memset(c,v,sizeof(c))
typedef long long ll;
const int N = 5e4 + 5;

struct Node{
    int val;  // 权值
    int tra;  // 陷阱
    bool vis; // 判断回头路
    ll dp[5][2];
}node[N];
vector <int > tree[N];
ll ans;
int n,c;

void dfs(int father){ // father,child(id)  nfather,nchild(node) 
    int size = tree[father].size();
    node[father].vis = true;
    Node& nfather = node[father];
    
    ///// init dp
    int& trap = nfather.tra;
    nfather.dp[trap][0] = nfather.dp[trap][1] = nfather.val;

    for(int i = 0 ; i < size ; i++){
        int  child  = tree[father][i];
        Node& nchild = node[child];
        if(nchild.vis)continue;
        dfs(child);
        for(int j = 0 ; j <= c ; j++){
            for(int k = 0 ; k+j <= c ; k++){
                if(j != c) // 若j==c了 那么在父节点得到的最大值就没有机会再往孩子下面走了 否则还有机会往下走
                    ans = max(ans , nfather.dp[j][0] + nchild.dp[k][1]); //所以转移是到父节点+另一个孩子回来
                if(k != c) // 同理
                    ans = max(ans , nfather.dp[j][1] + nchild.dp[k][0]); 
                if(j + k < c)// 以nfather为衔接点 当i+k==c的时候有(1||2)个端点一定在陷阱上
                    ans = max(ans , nfather.dp[j][0] + nchild.dp[k][0]); 
                    
                //ans = max(ans , nfather.dp[j][1] + nchild.dp[k][1]); 
            }
        }
        for(int j = 0 ; j <= c ; j++){
            if(j+trap>c)break;
            nfather.dp[j+trap][0] = max(nfather.dp[j+trap][0] , nfather.val + nchild.dp[j][0]);    
            if(j) // 当前机会数 必须大于0才能网上推
            nfather.dp[j+trap][1] = max(nfather.dp[j+trap][1] , nfather.val + nchild.dp[j][1]);    
        }
    }
}

int main(){
    //ReadFile("in.txt");
    int T;cin >> T;
    while(T--){
        cin >> n >> c;
        for(int i = 0 ; i < n ; i++){
            scanf("%d %d", &node[i].val, &node[i].tra);
            node[i].vis = false;
            CLR(node[i].dp,0);
        }
        for(int i = 1 ; i < n ; i++){
            int u,v;
            scanf("%d %d", &u, &v);
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        ans = 0;
        dfs(0);
        cout << ans << endl;
        for(int i = 0; i <= n ; i++)
            tree[i].clear();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/x314542916/article/details/9613585