HDU 4044：GeoDefense 树形DP+分组背包 GeoDefense
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4044
题意：
GeoDefense是一款游戏，规则差不多如下：
有一颗树，其根节点（1）是敌人基地，会派敌军出来，敌军可以走任何的路径，如果敌军走到了你的基地，那么你就输了，所有叶子节点都是你的基地。
敌军有一个HP值（未知），你可以在所有的节点上制造最多一个塔（需要花钱），每个塔有一个攻击力，没当敌军走到这个节点上就会对齐造成相当于塔的攻击的的伤害（HP-=攻击力），求在获胜的前提下HP的最大值。
输入一个T（表示有T组测试数据）
输入一个N，有N个点，接着是N-1对数据（a,b），表示a到b有边
输入一个m，表示你总共拥有m钱
紧接着是N行，第 i 行的第一个数据Ki表示在第 i 号点有Ki种塔，再次之后是Ki对数据，每对数据表示 i 点 可以造的第 j 种塔所要的花费以及该塔的攻击力
题解：
设dp[i][j]为在节点i上花费j元可以取得的最大收益，即终点状态为dp[1][M]，很容易知道dp[i][j]的值分别由 i 的子节点与 i 处塔本身的攻击得到。
因此可以将 j 拆分为j1，j2两部分：
①将j1分配给 i 的子节点，找出一种分配使得子节点中的最小值最大，这个值就是j1部分的值。
②j2部分则只需要对 i 处的塔进行一次贪心就可以得到。
枚举即可得到max(j1部分+j2部分)
代码
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int N=1001;
const int M=201;
const int L=51;
vector<int>q[N];
bool mark[N];
int dp[N][M];//在节点i上花费j元可以取得的最大收益
struct node
{
int amo,price[L],power[L];
}t[N];
int mmax(int x,int y)
{
return x>y?x:y;
}
int mmin(int x,int y)
{
return x<y?x:y;
}
void Dfs(int id,int m)
{
mark[id]=true;
bool fork=false;
int a[M]={0};
for(int i=0;i<q[id].size();++i)
{
int v=q[id][i];
if(mark[v])continue;
Dfs(v,m);
if(!fork)
{
fork=true;
for(int j=0;j<=m;++j)
a[j]=dp[v][j];
continue;
}
for(int j=m;j>=0;--j)
{
int ms=0;
for(int k=0;k<=j;++k)
ms=mmax(ms,mmin(a[j-k],dp[v][k]));
a[j]=ms;
}
}
for(int i=1;i<=t[id].amo;++i)
for(int j=m;j>=t[id].price[i];--j)
{
if(t[id].power[i]>dp[id][j])
dp[id][j]=t[id].power[i];
}
for(int i=m;i>=0;--i)
{
int ms=0;
for(int j=0;j<=i;++j)
{
if(dp[id][i-j]+a[j]>ms)
ms=dp[id][i-j]+a[j];
}
dp[id][i]=ms;
}
}
void clean(int n)
{
memset(dp,0,sizeof(dp));
memset(mark,false,sizeof(mark));
for(int i=1;i<=n;++i)
q[i].clear();
}
void solve()
{
int n,m,T,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
clean(n);
for(int i=1;i<n;++i)
{
scanf("%d%d",&a,&b);
q[a].push_back(b);
q[b].push_back(a);
}
scanf("%d",&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&t[i].amo);
for(int j=1;j<=t[i].amo;++j)
scanf("%d%d",&t[i].price[j],&t[i].power[j]);
}
Dfs(1,m);
printf("%d
",dp[1][m]);
}
}
int main()
{
solve();
return 0;
}