Vijos 1395 HYH的逻辑电路 解题报告

采用f[node,boolean]来描述一个状态，表示节点node输出boolean时，需要改变的最少节点数。状态转移按照节点node的运算符，枚举两个儿子节点的输出，分为And、Or和Xor三种情况进行转移：

And的情况：
f[i,0]:=min(f[lson,0]+f[rson,0],min(f[lson,1]+f[rson,0],f[lson,0]+f[rson,1]));
f[i,1]:=f[lson,1]+f[rson,1];

Or的情况：
f[i,0]:=f[lson,0]+f[rson,0];
f[i,1]:=min(f[lson,1]+f[rson,1],min(f[lson,1]+f[rson,0],f[lson,0]+f[rson,1]));

Xor的情况：
f[i,0]:=min(f[lson,0]+f[rson,0],f[lson,1]+f[rson,1]);
f[i,1]:=min(f[lson,1]+f[rson,0],f[lson,0]+f[rson,1]);

从根元件开始递归求解即可，最后输出的是根元件两种状态的较大者。

R1142172 Accepted 100 From IwfWcf－ P1395 FPC Vivid Puppy 2009-2-11 13:36:30