poj2411Mondriaan's Dream<DP>

链接: http://poj.org/problem?id=2414

题意:

　　一颗完全二叉树,有 N ( n <= 1024,且必定为2的整数幂,意味着是一颗完全二叉树 ) 个叶子节点, 每一个节点都含有一个长度为 L L ( L <= 1000 ) 的串 ( 串仅由大写字母构成), 现仅仅知道N个叶子节点串的组成.其他节点串不知道,若直接父节点相同的两个子节点,其对应位置不同则花费为1. 整棵树花费最小;

思路:

　　对于同一父亲节点上的两个子节点, 在相同位置上的字符如果相同, 那么它们的父亲节点在该位置唯一确定, 且花费不变, 对于不同的字符, 我们要保留它们两个的信息, 都传给父亲节点,用来与父亲节点的兄弟比较, 且花费加 1 ;

在编码上由于只有26个字母, 且状态只有两种我们就可以用一个 int 型整数来保留它们的信息, 实现状态压缩;

#include<stdio.h>
int N, L, T[2050], i, j,ans;
char s[1025][1025];
int main( )
{
    while( scanf( "%d%d", &N, &L )==2, N+L){
        for( i=0; i<N; ++ i )
            scanf( "%s", s[i] );
        for( i=0, ans=0; i<L; ++ i ){
            for( j=0; j<N; ++ j ){
                T[N+j]= 1<<(s[j][i]-'A');    
            }
            for( j=N-1; j>=1; --j ){
                if( (T[j]=T[j<<1]&T[(j<<1)+1])==0 ){//  交集等于0, 表示没有相同的字母, 需要改变  
                    ans++;
                    T[j]= T[j<<1] | T[(j<<1)+1];//  求并集, 即 把两个子节点的所有信息保留 
                }    
            }
            for ( j = 0; j < 26; ++j) {
                if (T[1] & (1 << j)) {
                    putchar('A' + j);
                    break;    
                }    
            } 
            
        }
        printf( " %d\n", ans );
    }
    return 0;
}