hdu 5148 樹形dp，分組背包

題目：

題目分析：

狀态方程： dp[目前節點的标号][目前已經選取的城市數]

設已經選取的城市數是K

初始狀态： dp[u][0] = dp[u][1] = 0 ， 其他的将值設定為無窮大

樹形轉移： dp[father][k] = min ( dp[father][k] , dp[father][k1] + dp[son][k-k1] + k1 *( k-k1)*weight_of_edge );

講解： 給出的點組成了一個樹形結構，而且是求取最優解，是以我們可以運用動态規劃，方程存的值是目前狀态下最小的子情況，我們可以利用分組背包進行狀态轉移，把每個子樹看做一組物品，每組物品中隻有已經選取的城市數不同，每件物品的花費是目前路徑在規劃中的總花費，這條邊下面子樹選取了k1個點，這條邊另一側要選取k-k1個點，是以一定有且僅有k1*(k-k1)t條路徑經過這條邊，是以花費可得

代碼如下，不懂可以在評論中提問，當天回複

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 4007

using namespace std;

struct 
{
    int v,next,w;
}e[MAX];

int t,k,n;
int head[MAX];
long long dp[MAX][57];
int cc;

void add ( int u , int v , int w  )
{
    e[cc].v = v;
    e[cc].w = w;
    e[cc].next = head[u];
    head[u] = cc++;
}

void dfs ( int u , int fa )
{
    dp[u][0] = 0;
    dp[u][1] = 0;
    for ( int i = head[u] ; i != -1 ; i = e[i].next )
    {
        int v = e[i].v;
        if ( v == fa ) continue;
        dfs ( v , u );
        for ( int j = k ; j >= 0 ; j-- )
        {
            for ( int t = 1 ; t <= j ; t++ )
                dp[u][j] = min ( dp[u][j] , dp[u][j-t] + (long long) dp[v][t] + (long long)(t*(k-t)* e[i].w ) );
        }
    }
}

int main ( )
{
    int a ,b , c ;
    scanf ( "%d" , &t );
    while ( t-- )
    {
        scanf ( "%d%d" , &n , &k );
        memset ( head , -1 , sizeof ( head ) );
        cc = 0;
        for ( int i = 1 ; i < n ; i++ )
        {
            scanf ( "%d%d%d" , &a , &b , &c  );
            add ( a , b ,c );
            add ( b , a ,c ); 
        }
        memset ( dp , 0x3f , sizeof ( dp ) );
        dfs ( 1 , -1 );
        printf ( "%lld\n" , dp[1][k]*2  );
    }
}