HDU 4003 Find Metal Mineral （树形DP，经典）

题意：给定一棵树图，n个节点，有边权，要派k<11个机器人从节点s出发，遍历所有的点，每当1只机器人经过1条边时就会花费该边的边权，边是可重复走的。问遍历完所有点的最小花费？

思路：

　　非常经典，首先需要知道一点，才能往下推理。就是“如果在t点派c个机器人往孩子u，那么最多只有1个机器人能走会回来到t，否则花费总是不划算的”。

　　稍微证明一下：

　　（1）假设派1个机器人往u，逛一圈回到u的父亲t，花费v= 子树u的边权和*2 + e(t,u)*2。若机器人不要了，那花费肯定比v还要少。

　　（2）假设派2个机器人往u，若要2个机器人都回来，显然花费要比（1）要大。若仅要1个机器人回来，花费仍比“仅派1只机器人往u”要高。（可以试试画一棵有3层的树，头两层只有1个节点，第三层节点数随意即可，来模拟一下就知道结果了）

　　得到的结论是，要么只派c个机器人去孩子u，且1个都不要走回来(注：0<c<=k)；要么派1个机器人出去，且遍历完子树u走回t。

　　这样已经很好解决了。枚举下点t的孩子数（组），再枚举点t可能获得的机器人数（容量），再枚举给这个孩子派的机器人数（物品）。

　　还有个初始化DP值的问题，因为每个孩子都是必须遍历的，而常规的分组背包是可选（至多选1件）或者不选物品的，那么可以先将“派1个机器人且回收1个机器人的DP值”丢进背包（保证了此容量下肯定有遍历过子树u），然后若有更好的状态再更新掉此容量。

　　用DP[t][0]表示“有1个机器人到达t遍历完子树再走回t”的花费。DP[t][i]表示“有i个机器人到达t且遍历完整棵子树t，且不要求回到t”的最小花费。

 #include <bits/stdc++.h>

 #include <cstdio>

 #include <cstring>

 #include <map>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL  long long

 using namespace std;

 const int N=;

 struct tower

 {

     int pri,pow;

 }tow[N][];

 struct node

 {

     int from,to,next;

     node(){};

     node(int from,int to,int next):from(from),to(to),next(next){};

 }edge[N*];

 int edge_cnt, head[N], cnt[N], dp[N][], n, m ;

 void add_node(int from,int to)

 {

     edge[edge_cnt]=node(from, to, head[from]);

     head[from]=edge_cnt++;

 }

 inline int cmp(tower a,tower b){return a.pri<b.pri;}

 void DFS(int t,int far)

 {

     node e;

     int flag=;

     for(int i=head[t]; i!=-; i=e.next)

     {

         e=edge[i];

         if(e.to==far)  continue;

         DFS(e.to, t);

         for(int j=m; j>=; j-- )  //容量

         {

             dp[t][j]=min(dp[t][j], dp[e.to][]);  //先装代价为0的，如果有更好的再代替掉。

             for(int k=; k<=j; k++ ) //给此孩子k元,得到的最大攻击力。

                 dp[t][j]=max(dp[t][j], min(dp[t][j-k], dp[e.to][k]));

         }

         flag=; //标记是否叶子。

     }

     if(flag==)    memset(dp[t], , sizeof(dp[t]));     //叶子节点

     //本节点的决策是“仅有1组的分组背包”模型： 必须且最多买1个。(不买就只能靠孩子来防御)

     for(int j=m; j>=; j-- )  //容量

     {

         int k=;

         for( ; k<cnt[t] && !tow[t][k].pri; k++ )  //不用钱的,只留1个power最大的.

             if(tow[t][k-].pow > tow[t][k].pow)

                 swap(tow[t][k],tow[t][k-]);

         for( k-- ; k<cnt[t]; k++)    //物品

         {

             if(j-tow[t][k].pri>=)

                 dp[t][j]=max(dp[t][j], dp[t][j-tow[t][k].pri] + tow[t][k].pow );    //可以直接挡

         }

     }

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t, a, b; cin>>t;

     while(t--)

     {

         edge_cnt=;

         memset(head, -, sizeof(head));

         memset(dp, 0x3f, sizeof(dp));   //注意初始化

         scanf("%d",&n);

         for(int i=; i<n; i++)  //无向图

         {

             scanf("%d%d",&a,&b);

             add_node(a,b);

             add_node(b,a);

         }

         scanf("%d",&m);     //钱。

         for(int i=; i<=n; i++)

         {

             scanf("%d",&cnt[i]);

             for(int j=; j<cnt[i]; j++)

                 scanf("%d%d", &tow[i][j].pri, &tow[i][j].pow);

             sort(tow[i], tow[i]+cnt[i], cmp);   //免费的排前面

         }

         DFS(, -);

         printf("%d\n",dp[][m]);

     }

     return ;

 }

AC代码

巴特西

HDU 4003 Find Metal Mineral （树形DP，经典）

最新文章

热门文章