<span>HDU4799 LIKE vs CANDLE（树形dp）</span>
题意：
若 干微博账户形成了一个转发树（即一个有根树）。每个账户有自己的价值，每个账户也有自己的态度（赞或蜡烛）。如果一个账户的态度是“赞”，它的价值就会被 加到“赞”的一边，反之亦然。Edward可以从“赞”的一边拿出X 的价值去翻转一个账户，即把它的态度换到相反的一边。但是Edward 发现，有的账户已经被别人翻转过了，对于这些账户，Edward就要花费Y的价值去翻转它们。一旦一个账户被翻转了一次，它的所有子账户也会被翻转一次。 求“赞”的一边的价值总数与“蜡烛”一边的价值总数的最大差值。若最大差值为负数则输出“HAHAHAOMG”。
输入：N个账户，X flip一个没有fliped的账户需要的花费，Y flip一个已经fliped的账户需要的花费。
四个数：账户价值，转发来源，是否要被flip（1表示要），被flip之前的状态（1表示蜡烛，0表示like）
思路：
dp[i][0]为第i个账户没有被翻转的最大价值，dp[i][1]为第i个账户被翻转的最大（负）价值
即dp[i][0]为赞减蜡烛的最大值，dp[i][1]为蜡烛减赞的最大值。
这样更新时
dp[u][0]直接可以由dp[v][0]或者dp[v][1]-(x or y)更新他
dp[v][0]更新dp[u][0]没什么好说的，子节点赞减蜡烛的最大值更新上一层
dp[v][1]-(x or y)更新dp[u][0]即为子节点被Edward翻转更新上一层
这样子节点的赞和蜡烛要被反转，而dp[v][1]保存的正是蜡烛减赞的最大值，翻转后正好是赞减蜡烛的最大值
然后再减去Edward翻转的消耗就可以了
/* *********************************************** Author :devil Created Time :2016/3/30 11:9:29 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; #define N 50010 int dp[N][2],n,x,y,v[N],f,s[N],p; bool vis[N],flag; vector<int>eg[N]; void init() { for(int i=0; i<N; i++) eg[i].clear(); memset(vis,false,sizeof(vis)); memset(dp,0,sizeof(dp)); flag=false; } void dfs(int u) { vis[u]=true; if(s[u]) flag^=1; if(flag) v[u]=-v[u]; dp[u][0]=v[u]; dp[u][1]=-v[u]; for(int i=0; i<eg[u].size(); i++) { int to=eg[u][i]; if(!vis[to]) { dfs(to); if(s[to]) { dp[u][0]=dp[u][0]+max(dp[to][0],dp[to][1]-y); dp[u][1]=dp[u][1]+max(dp[to][1],dp[to][0]-y); } else { dp[u][0]=dp[u][0]+max(dp[to][0],dp[to][1]-x); dp[u][1]=dp[u][1]+max(dp[to][1],dp[to][0]-x); } } } if(s[u]) flag^=1; } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d%d%d",&n,&x,&y)) { init(); for(int i=1; i<=n; i++) { scanf("%d%d%d%d",&v[i],&f,&s[i],&p); if(p) v[i]=-v[i]; eg[f].push_back(i); } dfs(0); if(dp[0][0]<0) printf("HAHAHAOMG\n"); else printf("%d\n",dp[0][0]); } return 0; }
投递快手等公司10个岗位 >
