bzoj 1864 [Zjoi2006]三色二叉树

bzoj 1864 [Zjoi2006]三色二叉树

​​ Description

Input 仅有一行，不超过500000个字符，表示一个二叉树序列。

Output 输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

Sample Input 1122002010

Sample Output 5 2 HINT

Source Day1

设dp[x][0/1]分别表示 该点是否被 染色成绿色的最多的点

dp[x][0]=max(dp[c[x][0]][1]+dp[c[x][1]][0],dp[c[x][0]][0]+dp[c[x][1]][1])

dp[x][1]=dp[c[x][0]][0]+dp[c[x][1]][0]

#include#include#include#includeusing namespace std;const int N=500050;int dp[N][2],c[N][2],n,p;char s[N];inline void dfs_init(){ ++p;if (p>n) return;int x=p; if (s[x]=='2'){ c[x][0]=p+1;dfs_init(); c[x][1]=p+1;dfs_init(); } if (s[x]=='1'){ c[x][0]=p+1;dfs_init(); }}inline void dfs(int x){ if (!x) return; dp[x][1]=1;dfs(c[x][0]);dfs(c[x][1]); dp[x][0]=max(dp[c[x][0]][1]+dp[c[x][1]][0],dp[c[x][0]][0]+dp[c[x][1]][1]); dp[x][1]+=dp[c[x][0]][0]+dp[c[x][1]][0];}inline void dfs1(int x){ if (!x) return; dp[x][1]=1;dfs1(c[x][0]);dfs1(c[x][1]); dp[x][0]=min(dp[c[x][0]][1]+dp[c[x][1]][0],dp[c[x][0]][0]+dp[c[x][1]][1]); dp[x][1]+=dp[c[x][0]][0]+dp[c[x][1]][0];}int main(){ freopen("bzoj1864.in","r",stdin); scanf("%s",s+1);n=strlen(s+1); dfs_init();dfs(1); printf("%d ",max(dp[1][0],dp[1][1])); memset(dp,0,sizeof(dp));dfs1(1); printf("%d\n",min(dp[1][0],dp[1][1])); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。