poj 2817 wordstack

數據規模很小，不免讓人想到搜索。但10！=3628800還是不夠優秀。

考慮到每次選擇只與前一次選擇有關，且N<=10，可以通過狀態壓縮的dp求解。

注意理解題意，允許兩個單詞中位置相同的字母不同，只是要求位置相同的字母相同的數目最大即可。

可以在dp前做一些預處理。

【代碼】

[cpp] 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <algorithm> 
using namespace std; 
 
int f[2][10][1<<10],g[12][12],len[10][10]; 
string s[10]; 
 
int main() 
{ 
    int i,j,k,m,n,x,la,lb,p,ans,tmp; 
 
    freopen("in","r",stdin); 
    while (1) 
    { 
        scanf("%d",&n); 
        if (n<=0) break; 
        memset(len,0,sizeof(len)); 
        for (i=0;i<n;i++) 
            cin >> s[i]; 
        for (i=0;i<n;i++) 
            for (j=0;j<n;j++) 
            if (i!=j) 
            { 
                la=s[i].size(); 
                lb=s[j].size(); 
                memset(g,0,sizeof(g)); 
                for (k=0;k<la;k++) 
                    for (p=0;p<lb;p++) 
                    { 
                        tmp=0; 
                        for (x=0;k+x<la && p+x<lb;x++) 
                            if (s[i][k+x]==s[j][p+x]) tmp++; 
                        len[i][j]=max(len[i][j],tmp); 
                    } 
 
            } 
        m=1<<n; 
        x=0; 
        memset(f[x],255,sizeof(f[x])); 
        for (i=0;i<n;i++) 
            f[x][i][1<<i]=0; 
        for (p=1;p<n;p++) 
        { 
            x^=1; 
            memset(f[x],255,sizeof(f[x])); 
            for (i=0;i<n;i++) 
                for (j=0;j<m;j++) 
                if (f[x^1][i][j]>=0) 
                    for (k=0;k<n;k++) 
                    if (((j>>k)&1)==0) 
                        f[x][k][j|(1<<k)]=max(f[x][k][j|(1<<k)],f[x^1][i][j]+len[i][k]); 
        } 
        ans=0; 
        for (i=0;i<n;i++) 
            ans=max(ans,f[x][i][m-1]); 
        printf("%d\n",ans); 
    } 
}