【题解】 bzoj1864: [Zjoi2006]三色二叉树 (动态规划)

时间:2022-11-01 06:57:28

bzoj1864,懒得复制,戳我戳我

Solution:

  • 其实想出来了\(dp\)方程推出来了最大值,一直没想到推最小值
  • \(dp[i][1/0]\)表示\(i\)号节点的子树中的绿色染色最大值,\(1\)表示该节点染色,\(0\)表示该节点不染色

\[dp[i][1]=dp[ls][0]+dp[rs][0]+1
\]

\[dp[i][0]=max(dp[ls][1]+dp[rs][0],dp[rs][1]+dp[ls][0])
\]
  • \(f[i][1/0]\)表示存的最小值,状态同上

\[f[i][1]=f[ls][0]+f[rs][0]+1
\]

\[f[i][0]=min(f[ls][1]+f[rs][0],f[rs][1]+f[ls][0])
\]

傻逼dp题卡了我好久

Code:

//It is coded by Ning_Mew on 4.20
#include<bits/stdc++.h>
#define ls(x) node[x].ch[0]
#define rs(x) node[x].ch[1]
using namespace std; const int maxn=5e5+7; int n,cnt=1,pl=-1;
struct Node{
int ch[2];
//Node(){ch[0]=-1;ch[1]=-1;}
}node[maxn];
int dp[maxn][2],f[maxn][2];
string s; void build(int u){
pl++;
if(s[pl]=='0'){dp[u][0]=0;dp[u][1]=1;f[u][0]=0;f[u][1]=1;return;}
if(s[pl]=='2'){
cnt++;node[u].ch[0]=cnt;build(cnt);
cnt++;node[u].ch[1]=cnt;build(cnt);
dp[u][1]=dp[ ls(u) ][0]+dp[ rs(u) ][0]+1;
dp[u][0]=max(dp[ ls(u) ][0]+dp[ rs(u) ][1],dp[ rs(u) ][0]+dp[ ls(u) ][1]);
f[u][1]=f[ ls(u) ][0]+f[ rs(u) ][0]+1;
f[u][0]=min(f[ ls(u) ][0]+f[ rs(u) ][1],f[ ls(u) ][1]+f[ rs(u) ][0]);
}
if(s[pl]=='1'){
cnt++;node[u].ch[0]=cnt;build(cnt);
dp[u][0]=dp[ ls(u) ][1];
dp[u][1]=dp[ ls(u) ][0]+1;
f[u][0]=f[ ls(u) ][0];
f[u][1]=f[ ls(u) ][0]+1;
}return;
}
int main(){
cin>>s;
build(1);
/*for(int i=1;i<=cnt;i++){
cout<<i<<' '<<node[i].ch[0]<<' '<<node[i].ch[1]<<endl;
}*/
printf("%d %d\n",max(dp[1][0],dp[1][1]),min(f[1][0],f[1][1]));
return 0;
}