Poj Solution 3192

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

#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

int index[7];
char sum[100];
char str[7][10];
int len[7];

int merge( int len, char *w, int l ) {
    int i = len-l, j;
    if( i<0 ) i = 0;

    for( ; i<=len; i++ ) {
        for( j=0; sum[i+j] && w[j] == sum[i+j]; j++ )
            ;
        if( sum[i+j] == 0 ) {
            for( ;j<l; j++ )
                sum[i+j] = w[j];
            return i+l;
        }
    }
    
    return -1; // never execute
}

int main( ) {
    int n, i, l, ans = 1000;
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        scanf( "%s", str[i] );
        len[i] = strlen( str[i] );
        index[i] = i;
    }

    do {
        l = 0;
        for( i=0; i<n; i++ ) {
            sum[l] = '';
            l = merge( l, str[ index[i] ], len[ index[i] ] );
        }

        if( l < ans )
            ans = l;
    }while( std::next_permutation( index, index+n ) );

    printf( "%dn", ans );

    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *