2013 ACM区域赛长沙 I LIKE vs CANDLE(ZOJ3734) 很好的一道树形DP
2024-10-01 04:29:10
题意:一棵有根树,每个节点都有一个value值和属性(zan或是 CANDLE)。你可以通过反转一些点的属性,反转一个点时候,它的整个子树都会被反转属性。有些点反转消耗代价为X,有些为Y。你的目标的是求zan和candle差的最大值。
思路:dp[i][0]代表zan比candle多的最大值,dp[i][1]代表zan比candle少的最大值。注意每次更新当前节点的状态,如果当祖先节点加上当前节点的反转状态为偶数当然val不变,否则变。此题信息比较多,注意化繁为简。转移方程见代码
#include<cstdio>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
vector<int>vec[maxn];
int dp[maxn][];
int val[maxn],flip[maxn];
int n,X,Y;
int u,p;
int dfs(int t,int st) {
st+=flip[t];
if(st&)
val[t]=-val[t];
dp[t][]=val[t];
dp[t][]=-val[t];
for(int i=; i<vec[t].size(); i++) {
dfs(vec[t][i],st);
int v=vec[t][i];
dp[t][]+=max(dp[v][],dp[v][]-(flip[v]?Y:X));
dp[t][]+=max(dp[v][],dp[v][]-(flip[v]?Y:X));
}
}
int main() {
// freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&n,&X,&Y)) {
for(int i=; i<=n; i++)
vec[i].clear();
for(int i=; i<=n; i++) {
scanf("%d%d%d%d",&val[i],&u,&flip[i],&p);
vec[u].push_back(i);
if(p) {
val[i]=-val[i];
}
}
dfs(,);
if(dp[][]<)
printf("HAHAHAOMG\n");
else
printf("%d\n",dp[][]);
}
return ;
}
最新文章
- WinMain初始化详细过程以及消息循环
- Delphi GDI+基本用法总结
- 定制属于自己的自动化安装的linux系统镜像
- TCP/IP协议原理与应用笔记07:HTTP、TCP/IP与socket区别
- 类 的继承性(Inherits)与 重写(Overrides)
- div的替代品
- docker疑难解答 -- 设置远程服务监听
- threejs - uv 映射 简要
- 常见jquery面试题
- Working with PDF files in C# using PdfBox and IKVM
- post 数据
- [BZOJ 2705] [SDOI 2012] Longge的问题
- 【nodejs】初识 NodeJS(四)
- springboot配置文件启动顺序
- ajax的基础
- 利用hadoop来解决“单表关联”的问题
- python标准库介绍——30 code 模块详解
- Java8系列之重新认识HashMap(转)
- 【洛谷】【扩欧】P1516 青蛙的约会
- WCF系列教程之WCF中的会话