hdu4044 GeoDefense

时间:2022-07-16 22:26:26

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4044

题意:一个树上的塔防游戏。给你n个结点的树,你要在树结点上建塔防御,在第 i 个结点上有 ki 种防御塔可供选择,每个塔给你建塔花费 pricei 和塔能造成的伤害 poweri (可以认为每个塔只能攻击一次),现在有一个怪物从结点1出发,随意的沿着树边去叶子结点,问你最坏的情况最大能对怪物造成多少伤害(即假设怪物会沿着受伤最小的路径走),开始有 m 单位钱

2<=n<=1000, 0<=ki<=50, 0<=pricei<=200, 0<=poweri<=5e4, 0<=m<=200

题解:树形dp,f[u][x]表示在以 u 为根的子树上花费 x 最多造成 f[u][x] 的伤害

考虑状态转移,对于当前结点u他有儿子 v1,v2,,,,vt,你现在有 x 单位钱,如何给这 t 个儿子分配使得伤害最小的儿子伤害最高?

依次遍历儿子,用maxSon[y]表示给到当前儿子为止总共花 y 单位钱,获得的最大收益

时间复杂度:O(n*m^2)

 /*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/10/6 星期二 22:57:51
* File Name: 1001.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; const int INF=0x7f7f7f7f; struct Graph {
struct Edge {
int u, v;
};
int n, m;
vector<Edge> edges;
vector<vector<int>> G;
vector<vector<pair<int,int>>> tower;
vector<vector<int>> f;
Graph(int _n):n(_n),m(),G(_n),tower(n),f(n){}
void addEdge(int u, int v) {
edges.push_back({u, v});
m=edges.size();
G[u].push_back(m-);
}
vector<int> & operator[](int x) {
return G[x];
}
}; int n, m;
void dfs(Graph & G, int u, int fa) {
auto & tower=G.tower[u];
auto & bag=G.f[u];
bag.assign(m+, );
for(const auto & p : tower) {
if(p.first>m) continue;
bag[p.first]=max(bag[p.first], p.second);
}
if(G[u].size()== && u!=) return;
vector<int> maxSon(m+, INF);
for(auto i : G[u]) {
const auto & e=G.edges[i];
if(e.v==fa) continue;
dfs(G, e.v, u);
const auto & vbag=G.f[e.v];
for(int j=m; j>=; --j) {
int mx=;
for(int k=; k<=j; ++k) {
mx=max(mx, min(maxSon[j-k], vbag[k]));
}
maxSon[j]=mx;
}
}
for(int v=m; v>=; --v) {
for(int i=; i<=v; ++i) {
if(maxSon[i]==INF) continue;
bag[v]=max(bag[v], bag[v-i]+maxSon[i]);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
Graph tree(n);
for(int i=; i<n-; ++i) {
int a, b;
scanf("%d%d", &a, &b);
--a; --b;
tree.addEdge(a, b);
tree.addEdge(b, a);
}
scanf("%d", &m);
for(int i=; i<n; ++i) {
int num;
scanf("%d", &num);
tree.tower[i].resize(num);
for(auto & p : tree.tower[i]) {
scanf("%d%d", &p.first, &p.second);
}
}
dfs(tree, , -);
int ans=;
for(auto x : tree.f[]) ans=max(ans, x);
printf("%d\n", ans);
}
return ;
}