题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4003
思路：dp[i][j]表示以i为根选择j个机器人的最小花费，然后就是背包了：dp[u][i]=min(dp[u][i],dp[u][i-j]+dp[v][j]+j*w)(1<<j<<i,u是v的根)。值得注意的是dp[u][0]的意义，dp[i][0]表示以i为根的子树派一个机器人遍历完整棵子树后又回到i的花费。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 #define MAXN 10100 8 #define inf 1<<30 9 10 struct Edge{ 11 int v,w; 12 Edge(int vv,int ww):v(vv),w(ww){} 13 }; 14 15 int n,s,k; 16 int dp[MAXN][20]; 17 vector<vector<Edge> >G; 18 19 void dfs(int u,int father) 20 { 21 for(int i=0;i<G[u].size();i++){ 22 int v=G[u][i].v,w=G[u][i].w; 23 if(v==father)continue; 24 dfs(v,u); 25 for(int i=k;i>=0;i--){ 26 dp[u][i]+=dp[v][0]+2*w;//v所在子树不放置机器人，那么必然要派一个机器人从u到v去遍历v所在子树并且回到u. 27 for(int j=1;j<=i;j++){ //子树放置1-j个机器人 28 dp[u][i]=min(dp[u][i],dp[u][i-j]+dp[v][j]+j*w); 29 } 30 } 31 } 32 } 33 34 int main() 35 { 36 int u,v,w; 37 while(~scanf("%d%d%d",&n,&s,&k)){ 38 G.clear(); 39 G.resize(n+2); 40 for(int i=1;i<n;i++){ 41 scanf("%d%d%d",&u,&v,&w); 42 G[u].push_back(Edge(v,w)); 43 G[v].push_back(Edge(u,w)); 44 } 45 memset(dp,0,sizeof(dp)); 46 dfs(s,-1); 47 printf("%d ",dp[s][k]); 48 } 49 return 0; 50 }