poj2486--Apple Tree(树状dp)

Description

Input

Output

Sample Input

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

Sample Output

11
2

题目大意：给出一个n个节点的树，每个节点上有个值，问不超过k步最高可以获得的值。i到j算一步，j到i也算一步

输入： 输入n和k，然后是n个节点的值，然后是n-1个i j代表了i和j节点相邻。根是1.

很容易看出来这是一个树状dp，dp[i][j]代表了以i节点为根，用j步可以得到的最大值，但是因为走到子树算是一步，走回到根也是一步，所以就要有两个dp关系，dp1[i][j]代表从i节点走j步又回到j节点的最大值，dp2[i][j]代表从i节点走j步不会到i节点的最大值。

那么状态转移方程为：当前节点为u，子树为v

回到i节点时：在节点u走j步，在子树v中走k步,从u到v和从v到u共走两步，那么在除v之外的其他子树走了j-k-2步。

dp1[u][j] = max(dp1[u][j],dp1[u][j-k-2]+dp1[v][k])

不回到i节点时：从节点u走j步

1.不在v子树中返回u，那么会在其他子树中返回u，在v中走k步，在u到v走一步，在除v外的子树走j-k-1步。

dp2[u][j] = max(dp2[u][j],dp1[u][j-k-1]+dp2[v][k])

2.在v子树中返回u，那么会在其他子树中存在不返回u的，在v中走k步，在u到v和v到u走两步，在除v之外的子树走j-k-2步。

dp2[u][j] = max(dp2[u][j],dp2[u][j-k-2]+dp1[v][k])

注意1：输入的节点i，j是相邻的关系，根是1。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std ;
struct tree{
    int v , next ;
}edge[110];
int head[110] , cnt ;
int dp1[110][210] , dp2[110][210] ;//dp1返回，dp2不返回 dp[i][j]:从i节点出发使用j步可以得到的最大值
int c[110] , n , m ;
void add(int u,int v) {
    edge[cnt].v = v ;
    edge[cnt].next = head[u] ;
    head[u] = cnt++ ;
    return ;
}
void dfs(int u) {
    int i , j , k , v ;
    dp1[u][0] = dp2[u][0] = c[u] ;
    if( head[u] == -1 )
        return ;
    for(i = head[u] ; i != -1 ; i = edge[i].next) {
        v = edge[i].v ;
        dfs(v) ;
    }
    for(i = head[u] ; i != -1 ; i = edge[i].next) {
        v = edge[i].v ;
        for(j = m ; j >= 0 ; j--) {
            for(k = 0 ; k <= j ; k++) {
                if( k+2 <= j ) {
                    dp1[u][j] = max(dp1[u][j],dp1[u][j-k-2]+dp1[v][k]) ;
                    dp2[u][j] = max(dp2[u][j],dp2[u][j-k-2]+dp1[v][k]) ;
                }
                if( k+1 <= j )
                dp2[u][j] = max(dp2[u][j],dp1[u][j-k-1]+dp2[v][k]) ;
            }
        }
    }
}
int Map[110][110] ;
queue <int> que ;
void bfs(int n) {
    while( !que.empty() ) que.pop() ;
    que.push(1) ;
    int i , u , v ;
    while( !que.empty() ) {
        u = que.front() ;
        que.pop() ;
        for(i = 1 ; i <= n ; i++){
            if( Map[u][i] == 1 ) {
                Map[u][i] = Map[i][u] = 0 ;
                add(u,i) ;
                que.push(i) ;
            }
        }
    }
}
int main() {
    int i , j , u , v ;
    while( scanf("%d %d", &n, &m) != EOF ) {
        memset(head,-1,sizeof(head)) ;
        memset(dp1,0,sizeof(dp1)) ;
        memset(dp2,0,sizeof(dp2)) ;
        memset(Map,0,sizeof(Map)) ;
        cnt = 0 ;
        for(i = 1 ; i <= n ; i++)
            scanf("%d", &c[i]) ;
        for(i = 1 ; i < n ; i++) {
            scanf("%d %d", &u, &v) ;
            Map[u][v] = Map[v][u] = 1 ;
        }
        bfs(n) ;
        dfs(1) ;
        int max1 = 0 ;
        for(i = 0 ; i <= m ; i++) {
            max1 = max(max1,dp2[1][i]) ;
        }
        printf("%d\n", max1) ;
    }
    return 0 ;
}