C++ 樹形DP經典例題詳解——二叉蘋果樹

引言

這是十分經典的樹形DP題，其轉移方程很好想到，但有一些坑要注意

題目描述

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

 現在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。 給定需要保留的樹枝數量，求出最多能留住多少蘋果。

輸入

第1行: 2個空格分開的整數，N 和 Q(1≤Q≤N,1＜N≤100)，N表示樹的結點數，Q表示要保留的樹枝數量。 接下來 N-1 行描述樹枝的資訊。 每行3 個整數，前兩個是它連接配接的結點的編号。第3 個數是這根樹枝上蘋果的數量。 每根樹枝上的蘋果不超過30000 個。

輸出

第1行：一個整數，表示最多能留住的蘋果的數量。

樣例輸入

Copy (如果複制到控制台無換行，可以先粘貼到文本編輯器，再複制)

5 2 
1 3 1 
1 4 10 
2 3 20 
3 5 20 
      

樣例輸出

21
      

思路

對于這一題，可以很快想到動态轉移方程

dp[ i ][ j ] = max ( dp[ i ][ j ] , dp[ i ][ j-k ] + dp[ s ][ k-1 ] + G[ x ][ s ] )

s 表示是 i 的兒子，G[ x ][ i ] 為該樹枝上的蘋果數、

我們可以想象一下，在 i 節點的子樹中，減去其兒子的 k 條邊，但不減去與兒子 s 節點的邊，就是隻減去了 k - 1 條邊

然後在實作的過程中，子樹的邊數是不好單獨求的，是以就在DFS中逐一求子樹的邊數

就用 sum += dfs( s , x ) 來求得邊數，在最後還要加一，應為還要算上自己的這條邊

代碼

結合代碼了解啦

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
 
int n , m , dis[107][107] , dp[107][107] ;
vector <int> G[107] ;
 
int dfs( int x , int fa )
{
    int sum = 0 ;
    for(int i = 0 ; i < G[x].size() ; ++ i )
    {
        int s = G[x][i];
        if( s == fa )
            continue;
        sum += dfs( s , x );//求邊數和
        sum = sum + 1 ;
        for(int j = m ; j >= 1 ; -- j ) {
            for(int k = 1 ; k <= j ; ++ k ) {//邊數算上自己必須減去一條
                dp[x][j] = max( dp[x][j] , dp[x][j-k] + dp[s][k-1] + dis[x][s] );
                //轉移求最優解
            }
        }
    }
    return sum;
}
 
int main()
{
    scanf("%d%d", &n , &m );
    for(int i = 1 ; i < n ; ++ i )
    {
        int a , b ,c ;
        scanf("%d%d%d", &a , &b , &c );
        dis[a][b] = dis[b][a] = c ;//表示 a 到 b 的邊權
        G[a].push_back(b);
        G[b].push_back(a);   
    }
    dfs( 1 , 0 );
    printf("%d", dp[1][m] );
    return 0;
}