hdu 2144(LCS+并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2144

思路：合并的过程中多了一个条件，而这个条件的判断可以通过求最长公共连续子序列得到，别的和普通的并查集没什么区别，最后就是简单地判断一下集合的个数即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 111
 7 char str[MAXN][MAXN];
 8 int len[MAXN];
 9 int dp[MAXN][MAXN];
10 int parent[MAXN];
11 int n;
12 double p;
13 
14 void Initiate()
15 {
16     for(int i=0;i<n;i++)
17         parent[i]=i;
18 }
19 
20 int Find(int x)
21 {
22     if(x==parent[x])
23         return x;
24     parent[x]=Find(parent[x]);
25     return parent[x];
26 }
27 
28 //最长公共连续子序列
29 int LCS(int a,int b)
30 {
31     int maxlen=0;
32     memset(dp,0,sizeof(dp));
33     for(int i=1;i<=len[a];i++)
34     {
35         for(int j=1;j<=len[b];j++){
36             if(str[a][i-1]==str[b][j-1]){
37                 dp[i][j]=dp[i-1][j-1]+1;
38                 if(dp[i][j]>maxlen)maxlen=dp[i][j];
39             }
40         }
41     }
42     return maxlen;
43 }
44 
45 
46 int main()
47 {
48     int ans,t=1;
49     while(~scanf("%d%lf",&n,&p))
50     {
51         for(int i=0;i<n;i++){
52             scanf("%s",str[i]);
53             len[i]=strlen(str[i]);
54         }
55         Initiate();
56         for(int i=0;i<n;i++)
57         {
58             for(int j=0;j<i;j++){
59                 int r1=Find(i);
60                 int r2=Find(j);
61                 if(r1==r2)continue;
62                 double pp=LCS(i,j)*100.0;
63                 if(pp/len[i]>p&&pp/len[j]>p)parent[r1]=r2;
64             }
65         }
66         ans=0;
67         for(int i=0;i<n;i++)if(parent[i]==i)ans++;
68         printf("Case %d:\n%d\n",t++,ans);
69     }
70     return 0;
71 }

View Code