首页 > 代码库 > zoj3734
zoj3734
题意:一棵有根树,每个节点都有一个value值和属性(LICK或是 CANDLE)。你可以通过反转一些点的属性,反转一个点时候,它的整个子树都会被反转属性。有些点反转消耗代价为X,有些为Y。你的目标的是使得LICK的value和最大。
解法:13年长沙区域赛一道题,感情当时都没有做到这道题。状态ans[i][0/1]分别表示此点的子树LICK最多能比CANDLE多多少和少多少的值。状态转移见代码。
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (_<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=50010; const LL INF=0x3FFFFFFF; int n,x,y; vector<int> vec[Max]; int value[Max]; int ans[Max][2]; bool flip[Max]; void dfs(int t,int st) { st+=flip[t]; if(st&1) value[t]=-value[t]; ans[t][0]=value[t]; ans[t][1]=-value[t]; for(int i=0;i<vec[t].size();i++) { dfs(vec[t][i],st); int p=vec[t][i]; ans[t][0]+=max(ans[p][0],ans[p][1]-(flip[p]?y:x)); ans[t][1]+=max(ans[p][1],ans[p][0]-(flip[p]?y:x)); } } int main() { while(cin>>n>>x>>y) { memset(ans,0,sizeof ans); for(int i=0; i<=n; i++) vec[i].clear(); for(int i=1; i<=n; i++) { int v,f,s,p; scanf("%d%d%d%d",&value[i],&f,&s,&p); flip[i]=s; if(p) value[i]=-value[i]; vec[f].push_back(i); } dfs(0,0); if(ans[0][0]<0) puts("HAHAHAOMG"); else cout<<ans[0][0]<<endl; } return 0; }
zoj3734
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。