ZOJ - 3201 Tree of Tree

题意：给你一棵树n个点的权值，求节点个数总的为k的最大的权值

思路：不算太难的树形DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 110;

int dp[MAXN][MAXN];
int val[MAXN],n,k;
vector<int> arr[MAXN];

void dfs(int u,int f){
    dp[u][1] = val[u];
    for (int i = 0; i < arr[u].size(); i++){
        int v = arr[u][i];
        if (v == f)
            continue;
        dfs(v,u);
        for (int j = k; j >= 1; j--)
            for (int l = 1; l+j <= k; l++)
                dp[u][j+l] = max(dp[u][j+l],dp[v][l]+dp[u][j]);
    }
}

int main(){
    while (scanf("%d%d",&n,&k) != EOF){
        for (int i = 0; i <= n; i++)
            arr[i].clear();
        int a,b;
        for (int i = 0; i < n; i++)
            scanf("%d",&val[i]);
        for (int i = 1; i < n; i++){
            scanf("%d%d",&a,&b);
            arr[a].push_back(b);
            arr[b].push_back(a);
        }
        memset(dp,-1,sizeof(dp));
        dfs(0,-1);
        int ans = 0;
        for (int i = 0; i < n; i++)
            if (dp[i][k] > ans)
                ans = dp[i][k];
        printf("%d\n",ans);
    }
    return 0;
}

ZOJ - 3201 Tree of Tree

原文：http://blog.csdn.net/u011345136/article/details/19052027