poj 2817 wordstack

数据规模很小，不免让人想到搜索。但10！=3628800还是不够优秀。

考虑到每次选择只与前一次选择有关，且N<=10，可以通过状态压缩的dp求解。

注意理解题意，允许两个单词中位置相同的字母不同，只是要求位置相同的字母相同的数目最大即可。

可以在dp前做一些预处理。

【代码】

[cpp]
#include
#include
#include
#include
#include
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 cin >> s[i];
for (i=0;i for (j=0;j if (i!=j)
{
la=s[i].size();
lb=s[j].size();
memset(g,0,sizeof(g));
for (k=0;k for (p=0;p {
tmp=0;
for (x=0;k+x if (s[i][k+x]==s[j][p+x]) tmp++;
len[i][j]=max(len[i][j],tmp);
}

}
m=1< x=0;
memset(f[x],255,sizeof(f[x]));
for (i=0;i f[x][i][1< for (p=1;p {
x^=1;
memset(f[x],255,sizeof(f[x]));
for (i=0;i for (j=0;j if (f[x^1][i][j]>=0)
for (k=0;k if (((j>>k)&1)==0)
f[x][k][j|(1< }
ans=0;
for (i=0;i ans=max(ans,f[x][i][m-1]);
printf("%d\n",ans);
}
}