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

题意:

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

思路:

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

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

1 #include
      
        2 int N, L, T[2050], i, j,ans; 3 char s[1025][1025]; 4 int main( ) 5 { 6     while( scanf( "%d%d", &N, &L )==2, N+L){ 7         for( i=0; i
       
        =1; --j ){14                 if( (T[j]=T[j<<1]&T[(j<<1)+1])==0 ){
    //  交集等于0, 表示没有相同的字母, 需要改变  15                     ans++;16                     T[j]= T[j<<1] | T[(j<<1)+1];//  求并集, 即 把两个子节点的所有信息保留 17                 }    18             }19             for ( j = 0; j < 26; ++j) {20                 if (T[1] & (1 << j)) {21                     putchar('A' + j);22                     break;    23                 }    24             } 25             26         }27         printf( " %d\n", ans );28     }29     return 0;30 }