題目鏈接：金屬采集

     思路：d(i, j)表示在以i為根結點的子樹中使用j個機器人的最小花費。設v為u的一個子節點，從節點i使用k個機器人收集以v為根結點的能量，狀態轉移方程為d(u, i) = min(d(u, i - k) + d(v, k) + cost * k)  1 <= k <= i. 注意d(u, i - k)表示用i - k個機器人去收集其他子樹的能量的最小花費，在遍歷所有子節點之后，d(u, i)的值才會固定。

   AC代碼：

#include <cstdio>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 1e5 + 5;int dp[maxn][12]; struct node{	int son, cost; 	node() {	}	node(int son, int cost):son(son), cost(cost) {	}};vector<node>road[maxn];int n, s, cnt;void dfs(int u, int PRe) { //u-當前節點，pre-它的父節點 	int n = road[u].size();	for(int i = 0; i < n; ++i) {		int v= road[u][i].son, cost = road[u][i].cost;		if(v == pre) continue;		dfs(v, u);		// 只考慮當前節點和已經發現的節點 		for(int k = cnt; k >= 0; --k) { //該子樹停留的機器人總數		//逆序枚舉--如果d(u, k)更新，那么不能影響d(u,k+1),如果順序枚舉會影響  			dp[u][k] += dp[v][0] + cost * 2; //讓一個機器人遍歷該子樹所有子節點并返回的花費 			for(int j = 1; j <= k; ++j) {    //至少一個機器人進入子樹 				dp[u][k] = min(dp[u][k], dp[u][k-j] + dp[v][j] + j * cost);			}		} 	} }int main() {		while(scanf("%d%d%d", &n, &s, &cnt) == 3) {		memset(dp, 0, sizeof(dp));		for(int i = 0; i <= n; ++i) road[i].clear();		int x, y, cost;		for(int i = 1; i < n; ++i) {			scanf("%d%d%d", &x, &y, &cost);			road[x-1].push_back(node(y-1, cost));			road[y-1].push_back(node(x-1, cost));		}		dfs(s - 1, -1);		printf("%d/n", dp[s - 1][cnt]); 	}	return 0;}如有不當之處歡迎指出！