POJ1699Best Sequence(DFS)

这题其实是由bug的一个串包含其它两个串的数据没有所以就这么水了它吧只处理两个串的关系就行了

回来补点。。看了huge的博客发现其实不是有Bug 题意没读清楚必须首尾相连像AGCT GC这样就不算。。降低了复杂

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define INF 0x3f3f3f
 8 char s[22][22];
 9 int k[22],o[22][22],n;
10 int vis[22],ans;
11 void init()
12 {
13     int i,j;
14     for(i = 1 ; i <= n ; i++)
15     {
16         for(j =  1; j <= n ; j++)
17         {
18             if(i==j)
19             continue;
20             o[i][j] = 0;
21             for(int g = 0 ; g < k[i] ; g++)
22             {
23                 if(s[j][0]==s[i][g])
24                 {
25                     int k1 = 1,k2 = g+1;
26                     while(k1<k[i]&&k2<k[j]&&s[j][k1]==s[i][k2])
27                     {
28                         k1++;
29                         k2++;
30                     }
31                     if(k1==k[i]||k2==k[j])
32                     {
33                         o[i][j] = k1;
34                         break;
35                     }
36                 }
37             }
38         }
39     }
40 }
41 void dfs(int x,int v,int sum)
42 {
43     if(sum>ans)
44     return ;
45     if(v==n)
46     {
47         ans = sum;
48         return ;
49     }
50     int i;
51     for(i = 1; i <= n ; i++)
52     {
53         if(!vis[i])
54         {
55             vis[i] = 1;
56             sum+=(k[i]-o[x][i]);
57             dfs(i,v+1,sum);
58             sum-=(k[i]-o[x][i]);
59             vis[i] = 0;
60         }
61     }
62 }
63 int main()
64 {
65     int i,t;
66     scanf("%d",&t);
67     while(t--)
68     {
69         memset(vis,0,sizeof(vis));
70         ans = INF;
71         scanf("%d%*c",&n);
72         for(i = 1 ; i <= n ;i++)
73         {
74             scanf("%s",s[i]);
75             k[i] = strlen(s[i]);
76         }
77         init();
78         for(i = 1; i <= n ;i++)
79         {
80             vis[i] = 1;
81             dfs(i,1,k[i]);
82             vis[i] = 0;
83         }
84         printf("%d
",ans);
85     }
86     return 0;
87 }

View Code