状态dp的一道比较简单的题，令dp[i][j]为第i个状态以第j个单词作为结尾所获得的最优解
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #define N 11 4 char s[N][N]; 5 int dp[1<<N][N]; 6 int mcs[N][N]; 7 int n; 8 int max(int a,int b) 9 { 10 return a>b?a:b; 11 } 12 void get_mc(int a,int b) 13 { 14 int len1=strlen(s[a]); 15 int len2=strlen(s[b]); 16 int i,j,k; 17 int maxa=0; 18 int res; 19 for(i=0;i<len1;i++) 20 { 21 res=0; 22 for(j=0;j<len2;j++) 23 { 24 if(i+j<len1&&s[a][i+j]==s[b][j]) 25 res++; 26 } 27 maxa=max(maxa,res); 28 } 29 for(i=1;i<len2;i++) 30 { 31 res=0; 32 for(j=0;j<len1;j++) 33 { 34 if(i+j<len2&&s[b][i+j]==s[a][j]) 35 res++; 36 } 37 maxa=max(maxa,res); 38 } 39 mcs[a][b]=mcs[b][a]=maxa; 40 } 41 int fun(int state,int last) 42 { 43 int i; 44 int statet=state; 45 statet^=(1<<(last-1)); 46 if(!statet) 47 return 0; 48 if(dp[state][last]!=-1) 49 return dp[state][last]; 50 int res; 51 int maxa=0; 52 for(i=0;i<n;i++) 53 { 54 res=0; 55 if(statet&(1<<i)) 56 res=fun(statet,i+1)+mcs[i+1][last]; 57 maxa=max(maxa,res); 58 } 59 return dp[state][last]=maxa; 60 } 61 int main() 62 { 63 int i,j,p; 64 while(scanf("%d",&n)&&n) 65 { 66 for(i=1;i<=n;i++) 67 scanf("%s",s[i]); 68 for(i=1;i<=n;i++) 69 for(j=i+1;j<=n;j++) 70 get_mc(i,j); 71 memset(dp,-1,sizeof(dp)); 72 p=(1<<n); 73 int maxa=0; 74 for(i=1;i<=n;i++) 75 maxa=max(maxa,fun(p-1,i)); 76 printf("%d\n",maxa); 77 } 78 return 0; 79 }