树型动态规划
首先根据给出的先序遍历序列建树，然后用两遍树型动态规划求出最大和最小值。假设绿色用0表示，1、2表示另外两种颜色。
表示以v为根的子树中根结点v的颜色为c时的绿色结点数最大值。当v为叶结点时，
而
；当v为非叶结点时，我们要给v的孩子结点分配不同于c的颜色，并在所有方案中去最大值，还有不要忘记当c为0时把根结点v自己加进去。求最小值与之类似，只要把所有的max都变为min即可。
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> using namespace std; int m,p,num[10011],cleft[10011],cright[10011],f[10011][3]; char s[10011]; int max(int a,int b,int c) { return max(max(a,b),c); } int min(int a,int b,int c) { return min(min(a,b),c); } void buildTree() { num[m]=s[p++]-'0'; if(num[m]==1) { cleft[m]=m+1; cright[m]=-1; ++m; buildTree(); return; } if(num[m]==2) { int t=m; cleft[t]=m+1; ++m; buildTree(); cright[t]=m; buildTree(); return; } if(num[m]==0) cleft[m]=cright[m++]=-1; } int getMax(int v,int c) { if(f[v][c]>-1) return f[v][c]; int r=(c==0); if(num[v]==1) r+=max(getMax(cleft[v],(c+1)%3),getMax(cleft[v],(c+2)%3)); else if(num[v]==2) r+=max(getMax(cleft[v],(c+1)%3)+getMax(cright[v],(c+2)%3),getMax(cleft[v],(c+2)%3)+getMax(cright[v],(c+1)%3)); return f[v][c]=r; } int getMin(int v,int c) { if(f[v][c]>-1) return f[v][c]; int r=(c==0); if(num[v]==1) r+=min(getMin(cleft[v],(c+1)%3),getMin(cleft[v],(c+2)%3)); else if(num[v]==2) r+=min(getMin(cleft[v],(c+1)%3)+getMin(cright[v],(c+2)%3),getMin(cleft[v],(c+2)%3)+getMin(cright[v],(c+1)%3)); return f[v][c]=r; } int main() { freopen("trot.in","r",stdin); freopen("trot.out","w",stdout); gets(s); buildTree(); memset(f,-1,sizeof(f)); printf("%d ",max(getMax(0,0),getMax(0,1),getMax(0,2))); memset(f,-1,sizeof(f)); printf("%d\n",min(getMin(0,0),getMin(0,1),getMin(0,2))); return 0; } |