树形dp hdu1561

有的堡垒攻克需要攻克另一个堡垒，形成一个森林，最多攻克m个堡垒，求获得宝物的最大价值。

1，以0做根将森林形成树；

2，用背包计算当前节点下需要攻克k个堡垒能获得的宝物最大价值，但是注意同一个根节点的情况不能够先后放入背包，否则会有比如1节点选2个和选三个形成了选5个，也就是某些节点重复计算了。所以要在back第j格时将所有种k依次放入，j--；

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<vector>

using namespace std;

const int maxa =  ;

int dp[maxa][maxa];

int back[maxa][maxa];

int vis[maxa][maxa];

int v[maxa];

vector<int> edge[maxa];

int numb[maxa];

int dfs(int x, int num ){//printf("%d %d\n", x, num);

    if(vis[x][num] || num == )

        return dp[x][num];

    memset(back[x], , sizeof(back[x]));

    for(int i = ; i < edge[x].size(); i ++){

        int k = edge[x][i];//printf("%d ", k);

        int last = -;

        for(int h = num-; h >= ; h--){

            for(int j = ; j <= h && j <= numb[k]; j++){

                int a = dfs(k, j);

                back[x][h] = max(back[x][h], back[x][h-j] + a);//printf("%d ", back[h]);

            }//puts("");

        }

    }

    vis[x][num] = ;

    return dp[x][num] = back[x][num-]+v[x];

}

int dfs1(int x){

    int sum =  ;

    for(int i = ; i < edge[x].size(); i++){

        int k = edge[x][i];

        sum += dfs1(k);

    }

    return numb[x] = sum +;

}

int main(){

int n, m;

   //freopen("in.cpp", "r", stdin);

    while(scanf("%d%d", &n, &m), n+m){

        memset(vis, , sizeof(vis));

        for(int i =; i <= n; i++)

            edge[i].clear();

        for(int i =; i <= n; i++){

            int a, b;

            scanf("%d%d", &a, &b);

            v[i] = b;

            edge[a].push_back(i);

        }

        dfs1();

            memset(dp, , sizeof(dp));

            printf("%d\n", dfs(, m+));

           /* for(int i = 0; i <= n; i++){

                printf("*%d ", numb[i]);

            }*/

    }

}

巴特西

树形dp hdu1561

最新文章

热门文章