题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4044
题目大意:给定n个节点组成的树,1为敌方基地,叶子结点为我方结点。我们可以在每个结点安放炮台,至多一炮,然后就可以打炮,每个结点有ki种炮,每种炮有一个花费和一个能量(能量对应着打掉敌人多少hp)。敌人可能往一个结点的每条分支跑,所以要想保证守住阵地,就要保证每个分支都要安放炮台。最后问怎么打炮,才能使打掉的敌人hp最多。
解题思路:树形DP+分组背包.要守住我方基地,只要从敌方基地开始打怪,让怪死在来我方基地的路上,这样就可以从根1开始进行状态转移。由于要保证我方每个基地都收住,所以每个结点都要先找出容量为j时儿子结点打掉的最小hp,这时可通过把儿子结点dp[v][j](dp[i][j]表示i结点用j费用打掉的最大hp)当作一个物品,每个v对应一组背包,然后计算max(t,min(dp[son][j-k],dp[v][k]))获得一个组合,容量为j,里面的最小值最大,赋值给dp[i][j]。
上面的过程是计算从儿子转移过来的情况,表示的是最坏的情况,然后我们要从当前结点中选择至多一个大炮,就是基础的分组背包。我预处理出了[i][j]表示的是i组物品费用为j能打掉最多的hp。这两段描述有点小乱,看代码直观些。。。
测试数据:10
4
1 2
1 3
3 4
0
1 0 30
2 0 30 0 100000
1 0 5000
1 0 5000
4
1 2
1 3
3 4
0
0
0
0
0
2
1 2
30
3 10 20 20 40 30 50
3 10 30 20 40 30 45
4
1 2
1 3
3 4
50
1 10 30
1 20 30
1 20 50
0
4
2 1
3 1
1 4
60
3 10 20 20 40 30 50
3 10 30 20 40 30 45
3 10 30 20 40 30 35
3 10 30 20 40 30 35
代码:#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MIN 210
#define MAX 1100
#define INF 2147483647
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
vector<int> tree[MAX];
int cost[MAX][MIN], hp[MAX][MIN];
int n, m, num[MAX], dp[MAX][MIN],tp[MAX][MIN]; //dp存放结果,tp相当于物品,费用为j价值为tp[i][j]
void Initial() {
memset(tp, 0, sizeof (tp));
for (int i = 1; i <= n; ++i)
tree[i].clear();
}
void Tree_DP(int son, int pa) {
int i, j, k, v,tot = tree[son].size();
if (son != 1 && tot == 1) {
//叶子结点
for (i = 0; i <= m; ++i)
dp[son][i] = tp[son][i];
return;
}
for (i = 0; i <= m; ++i) //非叶子结点必须保证从子节点或得一个可以打掉的最小hp
dp[son][i] = INF;
for (i = 0; i < tot; ++i) {
v = tree[son][i];
if (v == pa) continue;
Tree_DP(v, son);
for (j = m; j >= 0; --j) {
int t = 0;
for (k = 0; k <= j; ++k) //把dp[v][k]当作一个物品
t = max(t,min(dp[son][j-k],dp[v][k]));//必须从v结点转移,所以要和之前的状态比较获得一个最小hp
dp[son][j] = t;
}
}
for (j = m; j >= 0; --j) //选择当前结点,分组背包
for (k = 0; k <= j; ++k)
dp[son][j] = max(dp[son][j], dp[son][j-k]+tp[son][k]);
}
int main() {
int i, j, k, a, b, t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
Initial();
for (i = 1; i < n; ++i) {
scanf("%d%d", &a, &b);
tree[a].push_back(b);
tree[b].push_back(a);
}
scanf("%d", &m);
for (i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
for (j = 1; j <= num[i]; ++j) {
scanf("%d%d", &cost[i][j], &hp[i][j]);
tp[i][cost[i][j]] = max(tp[i][cost[i][j]],hp[i][j]);
}
}
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
tp[i][j] = max(tp[i][j],tp[i][j-1]);
Tree_DP(1, 0);
printf("%d\n", dp[1][m]);
}
}
本文ZeroClock原创,但可以转载,因为我们是兄弟。
分享到:
相关推荐
动态规划DP题解 POJ HDU部分动态规划DP题解
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
杭电hdu acm资料所用杭电的acm题
HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
杭电ACM课件2014版之 (HDUACM201403版_04)递推求解
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
杭电的ACM课件2014版之(HDUACM201303版_01)初识ACM
HDUACM201303版_10搜索入门
杭电ACM课件2014版之 (HDUACM201403版_08)计算几何基础
杭电ACM课件2014版之HDUACM201403版_10)搜索入门
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
杭电ACM课件2014版之 (HDUACM201403版_03)贪心算法
杭电ACM课件2014版之 (HDUACM201403版_05)动态规划
杭电ACM课件2014版之(HDUACM201403版_12)组合博弈入门