题目链接:http://poj.org/problem?id=1699
题目思路:先用kmp算最大匹配,然后问题就转化成了一个TSP问题,直接用状态压缩dp求解即可。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int t,n;
char str[110][110];
int share[12][12];
int flag[12];
int dp[1<<10][11];
int next[30];
void getnext(char *B,int len)
{
int i=0;
int j=-1;
next[0]=-1;
while(i<len)
{
if(j==-1||B[i]==B[j])
{
i++,j++,next[i]=j;
}
else
j=next[j];
}
}
int kmp(char *A,char *B,int a,int b)
{
int i=0;
int j=0;
while(i<a&&j<b)
{
if(j==-1||A[i]==B[j])
{
i++;j++;
}
else j=next[j];
}
return j;
}
int len[12];
int main()
{
int i,j,k,n,tmp;
scanf("%d",&t);
while(t--)
{
memset(flag,0,sizeof(flag));
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
len[i]=strlen(str[i]);
// printf("%d\n",len[i]);
}
for(i=0;i<n;i++)
{
getnext(str[i],len[i]);
for(j=0;j<n;j++)
{
if(i!=j&&!flag[j]&&kmp(str[j],str[i],len[j],len[i])==len[i])
{
// printf("ak");
flag[i]=1;
break;
}
}
}
int cnt=0;
for(i=0;i<n;i++)
{
if(!flag[i])
strcpy(str[cnt++],str[i]);
}
// printf("cnt %d\n",cnt);
for(i=0;i<cnt;i++)
len[i]=strlen(str[i]);
for(i=0;i<n;i++)
{
getnext(str[i],len[i]);
for(j=0;j<n;j++)
{
share[j][i]=kmp(str[j],str[i],len[j],len[i]);
}
}
for(i=1;i<(1<<cnt);i++)
for(j=0;j<cnt;j++)
{
dp[i][j]=inf;
if((i&(1<<j))!=0)
{
tmp=i-(1<<j);
if(tmp==0)
{
dp[i][j]=len[j];
continue;
}
for(k=0;k<cnt;k++)
{
if((tmp&(1<<k))!=0)
{
dp[i][j]=min(dp[i][j],dp[tmp][k]+len[j]-share[k][j]);
}
}
}
}
int ans=inf;
for(i=0;i<cnt;i++)
{
ans=min(ans,dp[(1<<cnt)-1][i]);
}
printf("%d\n",ans);
}
}
分享到:
相关推荐
poj 1699的代码和方法说明,个人原创
poj 1619 EKG Sequence.md
北大POJ1019-Number Sequence 解题报告+AC代码
poj 2442 Sequence.md
poj 3623 Best Cow Line, Gold.md
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码