Ural 1018 Binary Apple Tree（樹形dp）

題意：一棵二叉蘋果樹，每個樹枝上都有蘋果，求剪枝後剩下Q根樹枝的時候的最大蘋果數量。（剪枝的時候不能連根拔起）

思路：TreeDP。先由題給出的關系建立一棵二叉樹，把邊上的蘋果移動到子結點，然後對樹進行自底而上的DP，狀态轉移方程式為：f[root][j]=max(f[root.lc][i]+f[root.rc][j-1-i])+val[root]，maxx）;意思就是說當根root要保留j個點=root的左孩子保留i個點的最大蘋果數+root的右孩子保留j-1-i個點的最大蘋果數+root點的蘋果數。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=103;
typedef struct
{
    int lc,rc;
    int val;
}Node;
Node tree[MAXN];
int m,n;
int arr[MAXN][MAXN];
int f[MAXN][MAXN];
int vis[MAXN];
void Create(int root)
{
    vis[root]=1;
    for(int i=1;i<=m;i++)
    {
        if(!vis[i]&&arr[root][i])
        {
            if(!tree[root].lc)
            tree[root].lc=i;
            else tree[root].rc=i;
            tree[i].val=arr[root][i];
            Create(i);
        }
    }
}
int TreeDP(int root,int e)
{
    if(!root||!e)return 0;
    if(f[root][e])return f[root][e];
    int maxx=0;
    int l,r;
    for(int i=0;i<e;i++)
    {
        l=TreeDP(tree[root].lc,i);
        r=TreeDP(tree[root].rc,e-i-1);
        maxx=max(l+r,maxx);
    }
    f[root][e]=maxx+tree[root].val;
    return f[root][e];
}
int main()
{
    memset(arr,0,sizeof(arr));
    memset(vis,0,sizeof(vis));
    memset(tree,0,sizeof(tree));

    scanf("%d %d",&m,&n);
    int l,f,v;
    for(int i=1;i<m;i++)
    {
        scanf("%d %d %d",&l,&f,&v);
        arr[l][f]=arr[f][l]=v;
    }
    Create(1);
    printf("%d\n",TreeDP(1,++n));
    return 0;
}