「BZOJ1864」[ZJOI2006] 三色二叉树
Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
题解
随便dp一下即可
f[i][0/1]表示i结点为绿/非绿色的绿色结点的最大个数
转移
f[x][1]=f[l[x]][0]+f[r[x]][0]+1;
f[x][0]=max(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]);
最小值类似
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<cstdio> #include<iostream> #include<cstring> #define inf 1000000000 using namespace std; int ans1,ans2,sz=1,cnt; int f[300005][2]; int l[300005],r[300005]; void read(int x) { char ch=getchar(); if(ch=='0')return; sz++;l[x]=sz;read(sz); if(ch=='2') { sz++;r[x]=sz;read(sz); } } void dp1(int x) { if(!x)return; dp1(l[x]);dp1(r[x]); f[x][1]=f[l[x]][0]+f[r[x]][0]+1; f[x][0]=max(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]); } void dp2(int x) { if(!x)return; dp2(l[x]);dp2(r[x]); f[x][1]=f[l[x]][0]+f[r[x]][0]+1; f[x][0]=min(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]); } int main() { read(1); dp1(1);ans1=max(f[1][1],f[1][0]); memset(f,0,sizeof(f)); dp2(1);ans2=min(f[1][1],f[1][0]); printf("%d %d\n",ans1,ans2); return 0; } |
计数器 9786960
OI 课件=>
OI 课件=>
orz 随便DP一下，