hdu1561--H - ACboy needs your help(樹形dp)

hdu1561--H - ACboy needs your help(樹形dp)

H - ACboy needs your help Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status

Description

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

Output

For each data set, your program should output a line which contains the number of the max profit ACboy will gain.

Sample Input

 2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0 

Sample Output

 3
4
6 

樹形dp第一題啊

題目給出的依賴關系，可以組成幾個樹，在虛擬一個root，節點0，這樣把所有的點連接到一起

樹形dp中，數組dp[i][j]表示，對於第i個節點來說，選取j個城市，可以達到的最大值，建樹完成後，dfs，遞歸到葉子節點，dp[葉子][1] = 葉子的權值，其他的都是0，然後回溯上來，回到父節點，dp[i][j] = max( dp[i][j],dp[i][j-k]+dp[v][k] ) v表示孩子節點，k表示在整個以v為根節點的子樹中選取k個城市，那麼在以i為根節點的城市只能選取j-k個了，這樣近似於將i的每一個子節點都看做分組背包中的一個組，進行分組背包的操作，來得到dp[i][j] （1<=j <= m）的最大的權值，然後逐層回溯。

注意1，增加的總的根root，所以要求的城市數m應該再加上1.

注意2，因為存在依賴關系，所以dp[i][1]一定是i節點的權值，之後的才是子節點可以改變的權值，所以dp[i][j],j應該大於等於2，而且k一定要小於j，留下的一個位置放第i個節點

#include 
#include 
#include 
using namespace std;
struct node{
    int v ;
    int next ;
} edge[1000000] ;
int head[300] , p[300] , cnt ;
int dp[300][300] ;
int n , m ;
void add(int u,int v)
{
    edge[cnt].v = v ;
    edge[cnt].next = head[u] ;
    head[u] = cnt++ ;
}
void dfs(int u)
{
    int i , v , j , k ;
    dp[u][1] = p[u] ;
    for(i = head[u] ; i != -1 ; i = edge[i].next)
    {
        v = edge[i].v ;
        dfs(v);
        for(j = m ; j >= 2 ; j--)
        {
            for(k = 0 ; k < j ; k++)
                dp[u][j] = max( dp[u][j], dp[u][j-k]+dp[v][k] );
        }
    }
}
int main()
{
    int u , v , i ;
    while( scanf("%d %d", &n, &m)!=EOF )
    {
        if(n == 0 && m == 0) break;
        memset(head,-1,sizeof(head));
        memset(dp,0,sizeof(dp));
        p[0] = cnt = 0 ;
        for(i = 1 ; i <= n ; i++)
        {
            scanf("%d %d", &u, &v);
            p[i] = v ;
            add(u,i);
        }
        m++ ;
        dfs(0);
        printf("%d\n", dp[0][m]);
    }
    return 0;
}