首页 > 代码库 > hdu4799 树型DP

hdu4799 树型DP

2024-08-15 14:13:35   217人阅读

题意：若干微博账户形成了一个转发树（即一个有根树）。每个账户有自己的价值，每个账户也有自己的态度（赞或蜡烛）。如果一个账户的态度是“赞”，它的价值就会被加到“赞”的一边，反之亦然。Edward可以从“赞”的一边拿出X 的价值去翻转一个账户，即把它的态度换到相反的一边。但是Edward 发现，有的账户已经被别人翻转过了，对于这些账户，Edward就要花费Y的价值去翻转它们。一旦一个账户被翻转了一次，它的所有子账户也会被翻转一次。求“赞”的一边的价值总数与“蜡烛”一边的价值总数的最大差值。若最大差值为负数则输出“HAHAHAOMG”。

输入：N个账户，X flip一个没有fliped的账户需要的花费，Y flip一个已经fliped的账户需要的花费。

四个数：账户价值，转发来源，是否要被flip（1表示要），被flip之前的状态（1表示蜡烛，0表示like）

题解：说实话觉得特别绕，dp[n][2]两个状态一个表示翻转能得到的最大价值，一个表示不翻转能得到的最大价值。翻转的花费在父节点那一层计算更好算，因为最终的0节点是无法操作的，所以在那算很方便。有个trick就是初始就被转过的点的影响依然在子节点中，所以要用sta标记，，，，

 1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include <cmath> 7 using namespace std; 8 typedef long long ll; 9 const ll INF = 1000000000000000000ll + 10 ;10 const double eps = 1e-8;11 const int maxn = 5e4 + 10;12 const double PI = acos(-1);13 int dp[maxn][2],head[maxn],val[maxn],ss[maxn],ff[maxn],cnt;14 bool sta;15 struct st{16     int to,nxt;17 }edge[maxn*2];18 int n,x,y;19 void add(int u,int v){20     edge[cnt].to = v;21     edge[cnt].nxt = head[u];22     head[u] = cnt;23     cnt++;24 }25 void dfs(int u,int pre){26     if(ss[u]) sta = !sta;27     if(sta) val[u] = -val[u];28     dp[u][0] = val[u];29     dp[u][1] = -val[u];30     for(int i = head[u];i != -1;i = edge[i].nxt){31         int v = edge[i].to;32         if(v == pre) continue;33         dfs(v,u);34         dp[u][0] += max(dp[v][0],dp[v][1] - (ss[v]?y:x));35         dp[u][1] += max(dp[v][1],dp[v][0] - (ss[v]?y:x));36     }37     if(ss[u]) sta = !sta;38 }39 void init(){40     cnt = 0;41     memset(dp,0,sizeof(dp));42     memset(head,-1,sizeof(head));43 }44 int main()45 {46   //  freopen("in.txt","r",stdin);47     while(~scanf("%d%d%d",&n,&x,&y)){48         init();49         int fr;50         for(int i = 1;i <= n;i++){51             scanf("%d%d%d%d",&val[i],&fr,&ss[i],&ff[i]);52             if(ff[i]) val[i] = -val[i];53             add(fr,i);54         }55         sta = false;56         dfs(0,-1);57         if(dp[0][0] < 0) cout<<"HAHAHAOMG"<<endl;58         else  printf("%d\n",dp[0][0]);59     }60         return 0;61 }

 

hdu4799 树型DP


联系
我们