hdu4003 树形dp+分组背包

3 1 1 1 2 1 1 3 1 3 1 2 1 2 1 1 3 1

3 2  
Hint
In the first case: 1->2->1->3 the cost is 3; In the second case: 1->2; 1->3 the cost is 2;

这道题我的解题报告如果看不懂，就结合kuangbin巨巨的一起来看，效果会好一些~

https://www.cnblogs.com/kuangbin/archive/2012/08/29/2661928.html

/** hdu 4003  树形dp+分组背包 题目大意：有n个点构成的一棵树，要求用K个机器人跑最小的距离把每个点都遍历到 解题思路：         对于其中一个顶点，对于它的所有子结点看做一个种类，每一类中包含价值分别为：dp[son][0],dp[son][1]....dp[son][k]重量分别为0~k的物品。 状态转移方程:dp[u][k]=min(dp[u][k],dp[u][k-j]+(dp[v][j]+j*edge[u].w));(与父节点建立联系必须有j*edge[u].w) 这样借助分组背包就可以搞定，但是这样仅仅能保证在每一类物品中取一种或不取时的最优解，而题目要求的是所有类中必须都选一个，因此我们首先用dp[u][0] 表示用一个机器人走遍全部顶点的解，后面状态转移即可。 值得一提的是：在dp进行顶点u时必须保证所有儿子结点的全部状态必须已经求出，因此要用到dfs */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std;  int head[10005],ip,dp[10005][11]; int n,s,K;  struct note {     int v,w,next; }edge[10005*2];  void init() {     memset(head,-1,sizeof(head));     ip=0; }  void addedge(int u,int v,int w) {     edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++; }  void dfs(int u,int pre) {     for(int i=head[u];i!=-1;i=edge[i].next)///相当于枚举所有的种类     {         int v=edge[i].v;         if(v==pre)continue;         dfs(v,u);         for(int k=K;k>=0;k--)///背包容量枚举         {             dp[u][k]+=dp[v][0]+2*edge[i].w;             for(int j=1;j<=k;j++)///该种类下所有的物品             {                 dp[u][k]=min(dp[u][k],dp[u][k-j]+(dp[v][j]+j*edge[i].w));             }         }     } } int main() {     while(~scanf("%d%d%d",&n,&s,&K))     {         init();         for(int i=0;i<n-1;i++)         {             int u,v,c;             scanf("%d%d%d",&u,&v,&c);             addedge(u,v,c);             addedge(v,u,c);         }         memset(dp,0,sizeof(dp));         dfs(s,-1);         printf("%d/n",dp[s][K]);     }     return 0; }