簡單樹形動态規劃（Ural 1018 Binary Apple Tree）

極限簡單題：

二叉蘋果樹（apple）

Ural 1018

【問題描述】

有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有隻有1個兒子的結點）。這棵樹共有N個結點（葉子點或者樹枝分叉點），編号為1~~N,樹根編号一定是1。我們用一根樹枝兩端連接配接的結點的編号來描述一根樹枝的位置。下面是一顆有4個樹枝的樹

現在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。

給定需要保留的樹枝數量，求出最多能留住多少蘋果。

不得不說出題人真是好人

題目最重要一個條件：

二叉！

二叉！！

二叉！！！（重要的事情說三遍）

真為我們省事

1為蘋果樹的根

2，3，4..就是它的叉

一條邊連接配接的一個父親和一個兒子

這裡我們存為x和y

#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
    int x,y,d,next;
    //x:這條邊所連接配接的父親
    //y：這條邊所連接配接的兒子
    //d:這個叉上長了多少個蘋果
    //next:上一條邊的編号
}a[];
int last[],n,k,len=;
//last[len]:len這個點最後一條和它相連的邊的編号
struct nodetr
{
    int l,r;
    nodetr()
    {
        l=;r=;
    }
}tr[];
int f[][];
bool bk[];
void ins(int x,int y,int c)//建邊
{
    len++;
    a[len].x=x;a[len].y=y;a[len].d=c;
    a[len].next=last[x];last[x]=len;
}
int mymax(int x,int y)
{
    return x>y?x:y;
}
void dfs(int x)//這裡用了多叉樹的方法來做得
{
    for (int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if (bk[y]==true)
        {
            bk[y]=false;
            f[y][]=a[k].d;
            if (tr[x].l==) tr[x].l=y;
            else tr[x].r=y;
            dfs(y);
        }
    }
}
int treedp(int x,int kk)//DP
{
//f[i][j]：i:到哪一個點惹;j:保留多少個點
    if (f[x][kk]!=-) return f[x][kk];//如果已經做過就直接輸出
    int maxx=;
    for (int i=;i<=kk-;i++)
    {
        int ll,rr,trl,trr;
        ll=i;
        rr=kk--i;
        //分為左右兩部分，分别保留ll個枝和rr個枝
        trl=treedp(tr[x].l,ll);
        trr=treedp(tr[x].r,rr);
        //分别DP一遍
        maxx=mymax(trl+trr+f[x][],maxx);
    }
    f[x][kk]=maxx;
    return maxx;
}
int main()
{
    scanf("%d%d",&n,&k);
    memset(last,,sizeof(last));
    int x,y,c;
    for (int i=;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        ins(x,y,c);
        ins(y,x,c);
    }
    memset(f,-,sizeof(f));
    memset(bk,true,sizeof(bk));
    bk[]=false;
    dfs();
    for (int i=;i<=n;i++) f[i][]=;
    f[][]=;
    printf("%d\n",treedp(,k+));
    return ;
}