poj2817状态压缩 升维

/*

两两求出字符串之间最大可以匹配的值

由已知状态推导出位置状态

状态s表示已经加入到集合中的字符串，0表示串i不存在，1存在

由于字符串的加入顺序会影响结果，所以增加一维来表示

dp[S][i]表示状态集合为S，且i是新加入S的字符串的最大值

*/

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

char a[][];

int dp[<<][],w[][],n;

void get(int x,int y)

{

    w[x][y]=w[y][x]=;

    int l1=strlen(a[x]),l2=strlen(a[y]),s=;

    for(int i=; i<l1; i++)

        for(int j=; j<l2; j++)

        {

            int k=;

            s=;

            while(i+k<l1&&j+k<l2)

            {

                if(a[x][i+k]==a[y][j+k])

                    s++;

                k++;

            }

            if(s>w[x][y])w[x][y]=w[y][x]=s;

        }

}

int main(){

    while(cin>>n,n){

        for(int i=;i<=n;i++)

            cin>>a[i];

        for(int i=;i<=n;i++)

            for(int j=i+;j<=n;j++)

                get(i,j);//得到i和j配对的最大值

        memset(dp,,sizeof dp);

        for(int i=;i<(<<n);i++)

            for(int j=;j<=n;j++){//枚举状态中存在的字符串作为旧状态中最后放进去的字符串

                if( !(i&(<<(j-))) )continue;

                for(int k=;k<=n;k++)//枚举每个不在状态中的字符串作为新状态中最后放进去的字符串

                    if(!(i&(<<(k-))))

                        dp[i|(<<(k-))][k]=max(dp[i|(<<(k-))][k],dp[i][j]+w[j][k]);

            }

        int ans=;

        for(int i=;i<=n;i++)

            ans=max(ans,dp[(<<n)-][i]);

        printf("%d\n",ans);

    }

}