博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 4044 GeoDefense
阅读量:6519 次
发布时间:2019-06-24

本文共 1320 字,大约阅读时间需要 4 分钟。

树形DP,和背包差不多。dp[now][x]表示now这个节点的子树上,花费为x的时候,获得的最大防御能力(保证敌方HP<=0)

#include
#include
#include
#include
using namespace std;const int maxn = 1000 + 10;int T, n, m;vector
tree[maxn];struct kind{ int price; int power; kind(int a, int b){ price = a; power = b; }};vector
v[maxn];bool vis[maxn];int dp[maxn][200 + 10];int flag[200 + 10], tmp[200 + 10];void init(){ for (int i = 0; i <= n; i++) tree[i].clear(); for (int i = 0; i <= n; i++) v[i].clear(); memset(vis, 0, sizeof vis); memset(dp, -1, sizeof dp);}void read(){ scanf("%d", &n); for (int i = 1; i <= n - 1; i++) { int u, v; scanf("%d%d", &u, &v); tree[u].push_back(v); tree[v].push_back(u); } scanf("%d", &m); for (int i = 1; i <= n; i++) { int ki; scanf("%d", &ki); while (ki--) { int pricei, poweri; scanf("%d%d", &pricei, &poweri); kind k(pricei, poweri); v[i].push_back(k); } }}void dfs(int now){ bool fail = 1; for (int i = 0; i
= v[now][i].price; j--) if (flag[j - v[now][i].price] != -1) dp[now][j] = max(dp[now][j], flag[j - v[now][i].price] + v[now][i].power); for (int i = 0; i <= m; i++) dp[now][i] = max(dp[now][i], flag[i]); for (int i = 0; i

 

转载于:https://www.cnblogs.com/zufezzt/p/5186148.html

你可能感兴趣的文章
我眼中的自动化测试框架设计要点
查看>>
FLIF:自由的无损图像格式
查看>>
Google开源Inception-ResNet-v2,提升图像分类水准
查看>>
Opera 出售细节曝光:昆仑出资1.68亿美元
查看>>
CentOS 5.3 下快速安装配置 PPTP ××× 服务器
查看>>
产品经理学习总结之技术和设计篇
查看>>
23种设计模式(15):备忘录模式
查看>>
java基础学习总结——IO流
查看>>
iOS获取APP ipa 包以及资源文件
查看>>
类加载器总结
查看>>
[1298]活动选择 山东理工OJ
查看>>
Go语言中通过结构体匿名字段实现方法的继承和重载
查看>>
LOJ 117 有源汇有上下界最小流
查看>>
数组遍历——Vue.js
查看>>
IBATIS 写BLOB字段遇到的问题
查看>>
Java集合--Map
查看>>
Dev gridControl 按回车增加一行
查看>>
Reapte控件的使用
查看>>
模拟手指或者鼠标单击和双击
查看>>
修改版的echojs支持iScroll
查看>>