HDU 4616 Game 트리 DP 검색

제목 설명:

Description 　　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.
Input 　　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.
Output 　　For each testcase, output the maximum total value of gifts you can get.
Sample Input

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 

Sample Output

146
158 

제목 분석:

n개의 점, 각 점마다 val과 하나의 트랙이 있고 n-1개의 변이 있으며 그 트랙이 값 c를 초과하지 않는 상황에서 가장 큰 val과 트랙을 구한다.깊이 검색한 적이 있습니다. (나중에 데이터의 원인을 증명하면 AC를 검색할 수 있습니다. 그러나 이 문제는 트리 DP의 문제입니다.)

코드는 다음과 같습니다.

검색 코드:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN=50050;
struct sa
{
    int u,v;
    int next;
}tree[MAXN<<1];
int T,n,c;
int dp[MAXN<<1][5];
int head[MAXN];
int val[MAXN];
int track[MAXN];
bool visit[MAXN];
int e;

void init()
{
    e=0;
    memset(dp,-1,sizeof(dp));
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v)
{
    tree[e].u=u;
    tree[e].v=v;
    tree[e].next=head[u];
    head[u]=e++;
}

int dfs(int id,int tra)
{

    if (tra==c) return 0;
    if (dp[id][tra]!=-1) return dp[id][tra];
    int u,v,tmp,t;
    u=tree[id].u;
    v=tree[id].v;
    tmp=val[v];
    t=tra+track[v];
    for(int i=head[v]; i!=-1; i=tree[i].next)
    {
        if (tree[i].v!=u)
          tmp=max(tmp,dfs(i,t)+val[v]);
    }
    dp[id][tra]=tmp;
    return dp[id][tra];
}

int main()
{
    int u,v;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&c);
        init();
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&val[i],&track[i]);
        }
        for(int i=1; i<n; i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        int ans=0;
        for(int i=0; i<e; i++)
        {
            ans=max(ans,dfs(i,track[tree[i].u])+val[tree[i].u]);
        }
        printf("%d
",ans);
    }
    return 0;
}

트리 dp 코드가 하나 더 있어요.

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN=50050;


int T;
int n,c;
vector<int>vec[MAXN];
int val[MAXN],track[MAXN];
bool vis[MAXN];
int dp[MAXN][5][2];//dp[i][j][0]  i  j        dp[i][j][1]       
int ans;

void DP(int u)
{
    vis[u]=1;
    dp[u][track[u]][1]=dp[u][track[u]][0]=val[u];
    int v;
    for(int i=0; i<vec[u].size(); i++)
    {
        v=vec[u][i];
        if (vis[v]) continue;
        DP(v);
        for(int j=0; j<=c; j++)
        {
            for(int k=0; j+k<=c; k++)
            {
                if (j<c) ans=max(ans,dp[u][j][0]+dp[v][k][1]);
                if (k<c) ans=max(ans,dp[u][j][1]+dp[v][k][0]);
                if (j+k<c) ans=max(ans,dp[u][j][0]+dp[v][k][0]);
            }
        }
        for(int j=0; j+track[u]<=c; j++)
           dp[u][j+track[u]][0]=max(dp[u][j+track[u]][0],dp[v][j][0]+val[u]);
        for(int j=1; j+track[u]<=c; j++)
           dp[u][j+track[u]][1]=max(dp[u][j+track[u]][1],dp[v][j][1]+val[u]);
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%d%d",&n,&c);
        for(int i=0; i<n; i++)  vec[i].clear();
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&val[i],&track[i]);
        }
        for(int i=1; i<n; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        DP(0);
        printf("%d
",ans);
    }
}