Poj Solution 2414

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

#include"stdio.h"
#include"string.h"


int best[1024][26];
int min[1024];
char m[1024][1001];
char answer[1001];
int n,l;

bool init()
{
    int i;
    scanf("%d %d",&n,&l);
    if(n==0&&l==0)
        return 0;
    for(i=0;i<n;i++)
        scanf("%s",m[i]);
    return 1;
}

inline int min_int(int a,int b)
{
    return a<b?a:b;
}

void doit(int k)
{
    int i,j;

    for(i=n/2-1;i<n-1;i++)
    for(j=0;j<26;j++)
        best[i][j]=2;


    for(i=0;i<n;i++)
    {
        best[(i+n-2)/2][m[i][k]-'A']--;
        min [(i+n-2)/2]=m[i][k]-'A';
    }
    
    for(i=n/2-2;i>=0;i--)
    {
        min[i]=0;
        for(j=0;j<26;j++)
        {
            best[i][j]=min_int(best[i*2+1][min[i*2+1]]+1,best[i*2+1][j])
                      +min_int(best[i*2+2][min[i*2+2]]+1,best[i*2+2][j]);
            if(best[i][j]<best[i][min[i]])min[i]=j;
        }
    }
}            
int main()
{
    int i,ans;
    while(init())
    {
        ans=0;
        if(n==1)strcpy(answer,m[0]);
        else for(i=0;i<l;i++)
        {
            doit(i);
            ans+=best[0][min[0]];
            answer[i]=min[0]+'A';
        }
        answer[l]='';
        printf("%s %dn",answer,ans);
    }
    return 0;
}