poj 2817 wordstack

資料規模很小，不免讓人想到搜尋。但10！=3628800還是不夠優秀。

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

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

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

【代碼】

#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);
    }
}