洛谷 2585 [ZJOI2006]三色二叉树——树形dp

题目：https://www.luogu.org/problemnew/show/P2585

可以把不是绿色的记成一种。仔细一想不会有冲突。如果自己是绿色，孩子的不同颜色不会冲突；如果自己不是绿色，自己的不是绿色的孩子对于自己就像二分图一样的感觉，所以总有方案使得不区分另外两种颜色也不会有冲突。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e5+5; int n,rt,tot,ls[N],rs[N],dp[N][2][2],p0;//是/否绿 最大/小 char ch[N]; void build(int &cr,int dep) {cr=++tot;if(ch[p0]=='0')p0++;else if(ch[p0]=='1')p0++,build(ls[cr],dep+1);elsep0++,build(ls[cr],dep+1),build(rs[cr],dep+1); } void dfs(int cr) {if(!ls[cr]){dp[cr][0][0]=dp[cr][0][1]=1;dp[cr][1][0]=dp[cr][1][1]=0;return;}else if(!rs[cr]){int v=ls[cr]; dfs(v);dp[cr][0][0]=dp[v][1][0]+1;dp[cr][0][1]=dp[v][1][1]+1;dp[cr][1][0]=max(dp[v][0][0],dp[v][1][0]);dp[cr][1][1]=min(dp[v][0][1],dp[v][1][1]);}else{int Ls=ls[cr],Rs=rs[cr];dfs(Ls); dfs(Rs);dp[cr][0][0]=dp[Ls][1][0]+dp[Rs][1][0]+1;dp[cr][0][1]=dp[Ls][1][1]+dp[Rs][1][1]+1;dp[cr][1][0]=max(dp[Ls][0][0]+dp[Rs][1][0],dp[Ls][1][0]+dp[Rs][0][0]);dp[cr][1][1]=min(dp[Ls][0][1]+dp[Rs][1][1],dp[Ls][1][1]+dp[Rs][0][1]);} } int main() {//freopen("TRO.IN","r",stdin);//freopen("TRO.OUT","w",stdout);scanf("%s",ch);n=strlen(ch);build(rt,1);dfs(rt);printf("%d %d\n",max(dp[rt][0][0],dp[rt][1][0]),min(dp[rt][0][1],dp[rt][1][1]));return 0; }

 

转载于:https://www.cnblogs.com/Narh/p/9676480.html

总结

以上是生活随笔为你收集整理的洛谷 2585 [ZJOI2006]三色二叉树——树形dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。