题解：P13466 [GCJ 2008 #2] Cheating a Boolean Tree

· · 题解

简单树形 DP。
显然设 f_{i,j} 为，若要使节点 i 上的值为 j \in \{0,1\}，则 i 子树内至少要修改多少逻辑门。特别地若不可以达成这个目标则 f_{i,j}=+\infin。

转移较长，可以看代码。

#include<bits/stdc++.h>
#define N 10010
using namespace std;
int n,m,v,f[N][2],g[N],c[N];
int main(){
    cin>>n; for(int t=1;t<=n;t++){
        cin>>m>>v; memset(f,0x3f,sizeof(f));
        for(int i=1;i<=(m-1)/2;i++) cin>>g[i]>>c[i];
        for(int i=(m+1)/2,j;i<=m;i++) cin>>j,f[i][j]=0;
        for(int i=(m-1)/2;i>=1;i--){
            if(!(g[i]==0&&c[i]==0)) f[i][0]=min(f[i][0],f[2*i][0]+f[2*i+1][0]+(g[i]==0));
            if(!(g[i]==0&&c[i]==0)) f[i][0]=min(f[i][0],f[2*i][1]+f[2*i+1][0]+(g[i]==0));
            if(!(g[i]==0&&c[i]==0)) f[i][0]=min(f[i][0],f[2*i][0]+f[2*i+1][1]+(g[i]==0));
            if(!(g[i]==0&&c[i]==0)) f[i][1]=min(f[i][1],f[2*i][1]+f[2*i+1][1]+(g[i]==0));
            if(!(g[i]==1&&c[i]==0)) f[i][0]=min(f[i][0],f[2*i][0]+f[2*i+1][0]+(g[i]==1));
            if(!(g[i]==1&&c[i]==0)) f[i][1]=min(f[i][1],f[2*i][1]+f[2*i+1][0]+(g[i]==1));
            if(!(g[i]==1&&c[i]==0)) f[i][1]=min(f[i][1],f[2*i][0]+f[2*i+1][1]+(g[i]==1));
            if(!(g[i]==1&&c[i]==0)) f[i][1]=min(f[i][1],f[2*i][1]+f[2*i+1][1]+(g[i]==1));
        }
        cout<<"Case #"<<t<<": ";
        if(f[1][v]>1e9) cout<<"IMPOSSIBLE\n"; else cout<<f[1][v]<<"\n";
    }
}