POJ 1699 Best Sequence（DFS）

題意：將幾個片段如圖所示方法縮成一個序列，求出最短這個序列。

思路：其實我也不知道怎麼做。。。。。看網上都用了DP。。。。。但是我不會。。。。。這個DP不錯，還有用KMP+状压DP做的

 1 //1699
 2 #include <iostream>
 3 #include <stdio.h>
 4 #include <string.h>
 5 #include <string>
 6 
 7 using namespace std;
 8 
 9 string str[13] ;
10 int dp[33][33],ans ,n,vis[23];
11 
12 void f(int i,int j)
13 {
14     int len1 = str[i].size() ;
15     int len2 = str[j].size() ;
16     int s = 0 ;
17     for(int k = 0 ; k <= len1 && k <= len2 ; k++)
18     {
19         bool flag = true ;
20         for(int h = 0 ; h < k ; h++)
21         {
22             if(str[i][len1-k+h] != str[j][h])
23             {
24                 flag = false ;
25                 break ;
26             }
27         }
28         if(flag == true)
29             s = k ;
30     }
31     dp[i][j] = len2-s ;
32 }
33 
34 void dfs(int now,int ceng,int len)
35 {
36     if(len >= ans) return  ;
37     if(ceng == n-1) ans = min(ans,len) ;
38     for(int i = 1 ; i <= n ; i++)
39     {
40         if(!vis[i])
41         {
42             vis[i] = 1 ;
43             dfs(i,ceng+1,len+dp[now][i]) ;
44             vis[i] = 0 ;
45         }
46     }
47 }
48 int main()
49 {
50     int T;
51     scanf("%d",&T) ;
52     while(T--)
53     {
54         scanf("%d",&n) ;
55         for(int i = 1 ; i <= n ; i++)
56             cin>>str[i] ;
57         for(int i = 1 ; i <= n ; i++)
58             for(int j = 1 ; j <= n ; j++)
59                 if(i != j) f(i,j) ;
60         memset(vis,0,sizeof(vis)) ;
61         ans = 99999999 ;
62         for(int i = 1 ; i <= n ; i++)
63         {
64             vis[i] = 1 ;
65             dfs(i,0,str[i].size()) ;
66             vis[i] = 0 ;
67         }
68         printf("%d
",ans) ;
69     }
70     return 0;
71 }

View Code