这道题主要有两个问题
1.建树 2.dp方程的转移
dp方程还是很好推的 dp[u][2]表示将u号节点染成绿色 其子树中的最大/最小绿色点数
转移的时候对该节点儿子个数进行讨论
走到叶子节点的时候对该节点赋初值 dp[u][2] = 1;
如果儿子个数为1 则任意一种颜色在其对应相反的两种颜色中取max 绿色再加一
否则就是相反颜色的儿子dp之和的两种情况取max dp[u][2]同样加一
然后建树就是dfs建树 以时间戳为点的编号来搞 如果该节点没儿子就直接返回
然后跑最小值的时候要记住给dp赋极大值
就这样子慢慢搞 这道题还是比较简单 (我的代码超级丑)
#include <bits/stdc++.h> using namespace std; const int N = 500000 + 5; int n,step,tot,head[N],nex[2 * N],tov[2 * N],dp[N][3],vv[3],ans_max,ans_min; char s[N]; void add(int u,int v) { tot ++; tov[tot] = v; nex[tot] = head[u]; head[u] = tot; } void build(int u) { int nd = u - 1; bool tag = false; step ++; if(s[nd] == '1') { add(u,u + 1); add(u + 1,u); build(u + 1); } else if(s[nd] == '0') return ; else { tag = true; add(u,u + 1); add(u + 1,u); build(u + 1); } if(tag) { add(u,step + 1); add(step + 1,u); build(step + 1); } } void dfs(int u,int fa) { int num = 0; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa) continue; num ++; dfs(v,u); } if(num == 0) dp[u][2] = 1; else if(num == 1) { for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa) continue; dp[u][2] = max(dp[v][1] + 1,dp[u][2]); dp[u][2] = max(dp[v][0] + 1,dp[u][2]); for(int j = 0;j <= 2;j ++) dp[u][0] = max(dp[v][j],dp[u][0]); for(int j = 0;j <= 2;j ++) dp[u][1] = max(dp[v][j],dp[u][1]); } } else { int c = 0; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa) continue; vv[++ c] = v; } dp[u][2] = max(dp[vv[1]][1] + dp[vv[2]][0] + 1,dp[u][2]); dp[u][2] = max(dp[vv[2]][1] + dp[vv[1]][0] + 1,dp[u][2]); dp[u][1] = max(dp[vv[1]][2] + dp[vv[2]][0],dp[u][1]); dp[u][1] = max(dp[vv[2]][2] + dp[vv[1]][0],dp[u][1]); dp[u][0] = max(dp[vv[1]][2] + dp[vv[2]][1],dp[u][0]); dp[u][0] = max(dp[vv[2]][2] + dp[vv[1]][1],dp[u][0]); } } void dfs2(int u,int fa) { int num = 0; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa) continue; num ++; dfs2(v,u); } if(num == 0) { dp[u][2] = 1; dp[u][0] = 0; dp[u][1] = 0; } else if(num == 1) { for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa) continue; dp[u][2] = min(dp[v][1] + 1,dp[u][2]); dp[u][2] = min(dp[v][0] + 1,dp[u][2]); for(int j = 0;j <= 2;j ++) dp[u][0] = min(dp[v][j],dp[u][0]); for(int j = 0;j <= 2;j ++) dp[u][1] = min(dp[v][j],dp[u][1]); } } else { int c = 0; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa) continue; vv[++ c] = v; //把自己的儿子存起来 } dp[u][2] = min(dp[vv[1]][1] + dp[vv[2]][0] + 1,dp[u][2]); dp[u][2] = min(dp[vv[2]][1] + dp[vv[1]][0] + 1,dp[u][2]); dp[u][1] = min(dp[vv[1]][2] + dp[vv[2]][0],dp[u][1]); dp[u][1] = min(dp[vv[2]][2] + dp[vv[1]][0],dp[u][1]); dp[u][0] = min(dp[vv[1]][2] + dp[vv[2]][1],dp[u][0]); dp[u][0] = min(dp[vv[2]][2] + dp[vv[1]][1],dp[u][0]); } } int main( ) { scanf("%s",s); int len = strlen(s); build(1); dfs(1,1); ans_max = max(dp[1][0],max(dp[1][1],dp[1][2])); memset(dp,0x3f3f3f3f,sizeof(dp)); dfs2(1,1); ans_min = min(dp[1][0],max(dp[1][1],dp[1][2])); printf("%d %d",ans_max,ans_min); return 0; }