2017.5.3 tree

TEST

最优构造树(Tree)

给出N个长度为L的单词，N为2的整数次幂，那么我们可以构造出一棵树，把给出的N个单词作为树的叶子，其他每个树上的节点也都是一个长度为L的单词，我们定义一条边的代价为它连接的两个节点所代表的单词对位比较不同位的数目，整棵树的代价为所有边的代价和。

             AC

     AC              AC

  AB     AC      BC     AC

上面这棵树的代价和就是2。(脑补箭头吧)

给出N个单词，求最优构造树的最小代价。

输入格式：

第一行两个整数N和L，N <= 1024, L <= 1000
接下来N行每行一个单词。
多组数据，以0 0结束。

输出格式：

一个数表示最小代价。

样例输入：

4 3
AAG
AAA
GGA
AGA

4 3
AAG
AGA
AAA
GGA

4 3
AAG
GGA
AAA
AGA

4 1
A
R
A
R

2 1
W
W

2 1
W
Y

1 1
Q

0 0

样例输出：

3
4
4
2
0
1  
0

Solution

观察后发现，每一位都是独立于别的位的

可以每一位进行状态压缩DP解决

节点编号*2为左节点，*2+1为右节点
数组里的数是状态压缩的字母可能
当左右儿子有可能字母相同时，肯定选这个相同的字母，代价就是左右儿子之和(未生成新的代价)

if(opt[i<<1][j] & opt[(i<<1)+1][j]){
        opt[i][j]=opt[i<<1][j] & opt[(i<<1)+1][j];
        ans[i][j]=ans[i<<1][j] + ans[(i<<1)+1][j];
}

当左右儿子完全没有可能的字母时，把它存下来，代价+1；

else{
        opt[i][j]=opt[i<<1][j] | opt[(i<<1)+1][j];
        ans[i][j]=ans[i<<1][j] + ans[(i<<1)+1][j]+1;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXS 1005
using namespace std;
int n,l,depth;
char s[MAXS];
long long opt[2050][1005];
int ans[2050][1005];
void PRE(){
    int i,j;
    for(i=1;i<=2*n;i++){
        for(j=0;j<l;j++){
            opt[i][j]=ans[i][j]=0;
        }
    }
}
void GO(int i,int x){
    opt[i+n-1][x]^=1<<(s[x]-'A');
}
void solve(){
    int i,j;
    for(i=n-1;i>=1;i--){
        for(j=0;j<l;j++){
            if(opt[i<<1][j] & opt[(i<<1)+1][j]){
                opt[i][j]=opt[i<<1][j] & opt[(i<<1)+1][j];
                ans[i][j]=ans[i<<1][j] + ans[(i<<1)+1][j];
            }
            else{
                opt[i][j]=opt[i<<1][j] | opt[(i<<1)+1][j];
                ans[i][j]=ans[i<<1][j] + ans[(i<<1)+1][j]+1;
            }
        }
    }
    int tot=0;
    for(i=0;i<l;i++){
        tot+=ans[1][i];
    }
    printf("%d\n",tot);
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    while(scanf("%d%d",&n,&l)!=EOF){
        if(n==0 && l==0)return 0;
        int i;
        PRE();
        for(i=1;i<=n;i++){
            scanf("%s",s);
            for(int j=0;j<l;j++){
                GO(i,j);
            }
        }
        solve();
    }
    return 0;
}