8.3 LIS LCS LCIS（完结了==！）

感觉这个专题真不好捉，伤心了，慢慢啃吧，孩纸

地址http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28195#overview

密码 acmore

这算是LCS里面最简单了的吧

解题方法见http://www.cnblogs.com/gj-Acit/p/3236384.html

下面随便贴上两段代码

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX(a,b) (a>b?a:b)
 4 
 5 char X[1002],Z[1002];
 6 int Com[1002][1002];
 7 
 8 int main()
 9 {
10     memset(X,0,sizeof(X));
11     memset(Z,0,sizeof(Z));
12     while(~scanf("%s%s", X, Z))
13     {
14         memset(Com,0,sizeof(Com));
15         int LenX = strlen(X), LenZ = strlen(Z);
16         for(int i=0;i<LenX;i++)
17         {
18             for(int j=0;j<LenZ;j++)
19             {
20                 if(X[i] == Z[j])Com[i+1][j+1] = Com[i][j]+1;
21                 else Com[i+1][j+1] = MAX(Com[i][j+1], Com[i+1][j]);
22             }
23         }
24         printf("%d
",Com[LenX][LenZ]);
25     }
26     return 0;
27 }

下面这个空间复杂度要小一些

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX(a,b) (a>b?a:b)
 4 
 5 char X[1002],Z[1002];
 6 int Com[2][1002];
 7 
 8 int main()
 9 {
10     memset(X,0,sizeof(X));
11     memset(Z,0,sizeof(Z));
12     while(~scanf("%s%s", X, Z))
13     {
14         memset(Com,0,sizeof(Com));
15         int LenX = strlen(X), LenZ = strlen(Z);
16         int key = 0;
17         for(int i=0;i<LenX;i++)
18         {
19             key = !key;
20             for(int j=0;j<LenZ;j++)
21             {
22                 if(X[i] == Z[j])Com[key][j+1] = Com[!key][j]+1;
23                 else Com[key][j+1] = MAX(Com[!key][j+1], Com[key][j]);
24             }
25         }
26         printf("%d
",Com[key][LenZ]);
27         memset(X,0,sizeof(X));
28         memset(Z,0,sizeof(Z));
29     }
30     return 0;
31 }

View Code

Problem B HDU 1513 Palindrome

这道题最开始就看到好多人MLE，就想肯定是开了5000*5000,那时候自己也还不知道可以压缩空间，况且5000*5000时限上应该也会超时才对，加上自己本来就没有看LCS和LIS的资料，就不打算做了，到后来，在网上看了O(nlogn)的解法，就想试着写写看，虽知道不尽不好写，还RE了好多次，比赛结束后才慢慢明白原来自己在吧问题转化时把数组开小了很多，至于如何转化，题解放在http://www.cnblogs.com/gj-Acit/p/3236384.html

后来改了半天，也想尽力把空间开小一点，最后只能是把转化后的数组开到了100 * 5000，虽然理论上应该要开5000 * 5000的，我想应该是本题数据比较水吧。最后总算是Ac了

2460 KB 109 ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXN 5005
 6 int A[100*MAXN];
 7 int x[80][1005];
 8 int num[80],d[MAXN];
 9 
10 int Binary_search(int l,int r,int num)
11 {
12     int mid ;
13     while(r-l>1)
14     {
15         mid = l+(r-l)/2;
16         if(d[mid]<num)l = mid;
17         else r = mid;
18     }
19     return l;
20 }
21 
22 int LIS(int N)
23 {
24     memset(d,0,sizeof(d));
25     int len = 0;
26     d[len] = 0;
27     for(int i=0;i<N;i++)
28     {
29        if(A[i]>d[len])
30        {
31            d[++len] = A[i];
32        }
33        else
34        {
35            int j = Binary_search(0, len, A[i]);
36            d[j+1] = A[i];
37        }
38     }
39     return len;
40 }
41 
42 int cmp(int a,int b)
43 {
44     return b<a;
45 }
46 
47 int Record(char *str)
48 {
49     memset(num,0,sizeof(num));
50     int len = strlen(str)-1;
51     int key = len;
52     while(len>=0)
53     {
54         x[(int)str[len] - '0'][num[(int)str[len] - '0']++] = key-len;
55         len--;
56     }
57     for(int i=0;i<80;i++)if(num[i])
58     {
59         sort(x[i], x[i] + num[i], cmp);
60     }
61     len = strlen(str);
62     int countt = 0;
63     for(int i=0;i<len;i++)
64     {
65         for(int j=0;j<num[(int)str[i] - '0'];j++)
66         {
67             A[countt++] = x[(int)str[i] - '0'][j];
68         }
69     }
70     return countt;
71 }
72 
73 int main()
74 {
75     int N; char str[MAXN];
76     while(~scanf("%d%*c", &N))
77     {
78         scanf("%s",str);
79         memset(A,0,sizeof(A));
80         int len = Record(str);
81         int ans = LIS(len);
82         printf("%d
", N-ans);
83     }
84     return 0;
85 }

然后后来居然后人用n^2 才300+Ms就过了，我不得不说数据的确很水了

276 KB 375 ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX(a,b) a>b?a:b
 4 
 5 int N,f[2][5005];
 6 char str1[5005],str2[5005];
 7 
 8 int LCS()
 9 {
10     memset(f,0,sizeof(f));
11     int key = 0;
12     for(int i=0;i<N;i++)
13     {
14         key = !key;
15         for(int j=0;j<N;j++)
16         {
17             if(str1[i] == str2[j])
18             {
19                 f[key][j+1] = f[!key][j]+1;
20             }
21             else f[key][j+1] = MAX(f[!key][j+1], f[key][j]);
22         }
23     }
24     return MAX(f[0][N], f[1][N]);
25 }
26 
27 int main()
28 {
29     while(~scanf("%d", &N))
30     {
31         scanf("%s", str1);
32         for(int i=0;i<N;i++)
33         {
34             str2[i] = str1[N-1-i];
35         }
36         printf("%d
", N-LCS());
37     }
38     return 0;
39 }

Problem C HDU 4545 魔法串

这道题我用的方法是，直接将各种变换存放在一个数组里面，并记录每个字母可以变化为其他字母的个数，这样在对a额b比较的时候，如若在a[i]之前的字母在b[j]之前都已经找到了匹配的字母，那么在比较a[i]和b[j]时，就直接现将a[i]和b[j]比较，如果相同的话那么i和j都直接挑到下一个，否者比较a[i]和可以替换b[j]的字母，如果有相同的，说明可以通过替换来让他们匹配起来，再否则，j直接跳到下一个，再和a[i]比较，直到有一个字符串找完。如果a找完了，说明匹配完了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define GetNum(b) ((int)b-'a')
 4 #define MAX(a,b) ( (a) > (b) ? (a) : (b) )
 5 
 6 char Xi[1001], Ming[1001], Exchange[26][100];//由于只有阿26个字母，所以前面设置大小为26
 7 int num[26], M, Case;
 8 
 9 int main()
10 {
11     int T=0;
12     while(~scanf("%d%*c", &Case))while(Case--)
13     {
14         memset(num, 0, sizeof(num));
15         memset(Exchange, 0, sizeof(Exchange));
16         scanf("%s %s",Xi,Ming);
17         scanf("%d%*c", &M);
18         char a,b;
19         for(int i = 0; i < M; i ++ )//直接将各种变换放在Exchange数组里面
20         {
21             scanf("%c %c%*c",&a, &b);
22             Exchange[ GetNum(a) ][ num[GetNum(a)] ++ ] = b;//num数组记录每个字母可以被替换的种数
23         }
24         int indexXi = 0, indexMing = 0, LenXi = strlen(Xi), LenMing = strlen(Ming);
25         while(indexXi < LenXi && indexMing < LenMing)
26         {
27             if(Xi[indexXi] == Ming[indexMing])//先和自身比较
28             {
29                 indexXi++;
30                 indexMing++;
31                 continue;
32             }
33             int flag = 1;
34             for(int i=0;i<num[GetNum(Ming[indexMing])]; i++)//再和Ming可以被替换的字母比较
35             {
36                 if(Xi[indexXi] == Exchange[GetNum(Ming[indexMing])][i])
37                 {
38                     flag = 0;
39                     indexMing ++;
40                     indexXi ++;
41                     break;
42                 }
43             }
44             if(flag)indexMing ++;//若都找不到，那么Ming直接跳到下一个
45         }
46         printf("Case #%d: %s
", ++T, (LenXi == indexXi) ? "happy" : "unhappy");
47     }
48     return 0;
49 }

Problem D HDU 1257 最少拦截系统

题解见http://www.cnblogs.com/gj-Acit/p/3238689.html

Problem E HDU 1677

Nested Dolls

题目的意思是说一些娃娃有大小不同的很多个，小的可以放进大的里面，前提条件是它的宽W和高H，都比大的要小。

其实最开始看到这个题我也不会，只是在之前受人的指点说这个题和第D题一样。而他的思路就是，先将这些娃娃先按照W（H也可以的）逆序排序，这样一来的话前面对娃娃都是W比后面大的，所以我们就只需要讨论H的比较。所以这时就只需要前面的娃娃的H比后面的要大的话，那后面的娃娃也就可以放进前面的娃娃里面，也就转化为了有一个序列，求最少严格递减子序列有多少个，也就转化为了上题。

有一点需要注意的就是，如果两个娃娃他们的W一样大的话，要按照他们的H从小到大排列。举个例子来说明：序列

W 6 6 6 6 6 5 5 5 5

H 6 5 4 3 2 1 2 4 5

目前是将W由逆序排序，H不排，（其实H按逆序排序分析结果是一样的），那么由于我们此时只考虑H而不考虑W，所以按照求最长升序子序列的方法（这里需要先知道一下求最长升序子序列nlogn的解法），W为6的H为6的那个娃娃会把W为5H为1的包含进去，W为6H为5的娃娃会把W为5H为2的包含进去，而之后W为6的却都不可以把之后w为5的放在它内部了，所以此时结果就是7，而实际上6->5,5->4,4->2,3->1我们就只需要5个娃娃就行了。

而最后将H升序排序的目的就是只将W比当前小的而且保证每个都尽量去包含与他H接近的哪一个娃娃，这样贪心结果就不会有错。

W 6 6 6 6 6 5 5 5 5

H 2 3 4 5 6 1 2 4 5

这里每个W为6的都可以包含以后W为5的娃娃了。所以是最优解。

贴代码

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define MAX(a, b) ( (a) > (b) ? (a) : (b))
 5 #define mem0(a) memset(a, 0, sizeof(a))
 6 using namespace std;
 7 
 8 struct node {int w,h;}Doll[20005];
 9 int f[20005];
10 int N,T;
11 
12 int cmp(node a,node b)
13 {
14     if(a.w != b.w)return a.w > b.w;
15     return a.h < b.h;
16 }
17 
18 int main()
19 {
20     while(~scanf("%d", &T))while(T--)
21     {
22         scanf("%d", &N);
23         mem0(Doll);  mem0(f);
24         for(int i=1;i<=N;i++)
25         {
26             scanf("%d%d", &Doll[i].w,&Doll[i].h);
27         }
28         sort(Doll+1, Doll+1+N,cmp);
29         int ans = 0;
30         for(int i=1;i<=N;i++)
31         {
32             int l = 0, r = ans, mid;
33             while(l<r)
34             {
35                 mid = (l+r)/2;
36                 if(f[mid] <= Doll[i].h) l = mid + 1;
37                 else r = mid;
38             }
39             f[l] = Doll[i].h;
40             if(l == ans) ans ++;
41         }
42         printf("%d
", ans);
43     }
44     return 0;
45 }

Problem F HDU 1423

Greatest Common Increasing Subsequence

裸的LCIS，百度之或见http://www.cnblogs.com/gj-Acit/p/3236384.html

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX(a, b) ( (a) > (b) ? (a) : (b) )
 4 int T, n1, n2, a, f[505], b[505];
 5 int main()
 6 {
 7     while(~scanf("%d", &T))while(T--)
 8     {
 9         memset(f,0,sizeof(f));
10         scanf("%d", &n2);
11         for(int i=1;i<=n2;i++) scanf("%d", &b[i]);
12         scanf("%d", &n1);
13         for(int i=1;i<=n1;i++)
14         {
15             scanf("%d", &a);
16             int maxx = 0;
17             for(int j=1;j<=n2;j++)
18             {
19                 if(a > b[j] && maxx < f[j]) maxx = f[j];
20                 if(a == b[j]) f[j] = maxx + 1;
21             }
22         }
23         int ans = 0;
24         for(int i=1;i<=n2;i++) ans = MAX(ans, f[i]);
25         printf("%d
", ans);
26         if(T)printf("
");
27     }
28     return 0;
29 }

Problem G HDU 4512

吉哥系列故事――完美队形I

题目大意就不介绍了。感觉这道题挺不错的。

这道题还是求最长公共上升子序列有多长，只是比上题复杂了一点点。

由于是要求两端相等但也要使得序列升序且最长，那我们就枚举中点mid（1~N），这样的话那我们就只需要比较a[1~mid]和a[N~mid]这两个区间的最升序长公共子序列的长度，再找到他们最长的长度。见代码：

 1 /*
 2 只有注释位置与普通的LCIS略有改动，其他都一样
 3 */
 4 int Max = 0;
 5 for(int mid = 1; mid <= N;mid ++)//枚举中点
 6 {
 7     mem0(f);
 8     int key=0,ans = 0;
 9     for(int i=1;i<=mid;i++)//左边区间从1~mid
10     {
11         int Maxx = 0;
12         for(int j=N;j>=mid;j--)//右边区间从N~mid
13         {
14             if(a[i] > a[j] && Maxx < f[j])Maxx = f[j];
15             if(a[i] == a[j])
16             {
17                 f[j] = Maxx+1;
18                 if(ans < f[j]*2)//如果更优，更新
19                 {
20                     ans = f[j]*2;
21                     if(j == mid)ans --;//如果j==mid,也就是说此时,而此时更优，也就是说mid更优，
22                                        //说明mid被计算在了最长的序列当中，那它就在*2时被计算了2次,所以-1
23                 }
24             }
25         }
26     }
27     Max = MAX(Max, ans);//找出最大的解
28 }
29 printf("%d
", Max);

我们再看看上面的代码：

for(int mid = 1;mid <= N; mid ++ )

{

　　for(int i = 1 ; i <= mid ; i ++ ) {

　　}

可以注意到在计算mid的时候，i从1~mid循环了一次，而计算mid+1时i从1~mid又计算了一次，而实际上这两次计算的结果f[N~(mid+1)]都是一样的（因为相当于a序列是a[1~mid],b序列是a[N~mid+1],两次计算他们的最长公共升序子序列的长度肯定是一样的），那么为了免去这个重复的计算，在mid取到mid+1的时候，i便直接从mid+1开始，就可以直接使用前面已经计算出来的mid的所有的值，而省去x从1~mid的重复计算。

所以这时我们就只需要两个循环，i表示的便是枚举的中点mid。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define MAX(a, b) ( (a) > (b) ? (a) : (b))
 5 #define mem0(a) memset(a, 0, sizeof(a))
 6 using namespace std;
 7 
 8 int a[205], f[205];
 9 int Case, N;
10 
11 int main()
12 {
13     while(~scanf("%d", &Case))while(Case--)
14     {
15         mem0(a);  mem0(f);
16         scanf("%d", &N);
17         for(int i=1;i<=N;i++)
18         {
19             scanf("%d", &a[i]);
20         }
21         int ans = 0;
22         for(int i=1;i<=N;i++)//i表示的是mid的值
23         {
24             int Max = 0, key = 0;
25             for(int j=N;j>=i;j--)//j依然从N取到mid(i)
26             {
27                 if(a[i] > a[j] && Max < f[j])Max = f[j];
28                 if(a[i] == a[j])
29                 {
30                     f[j] = Max+1;
31                     if(ans < f[j]*2)
32                     {
33                         ans = f[j]*2;
34                         key = j;//记录两个序列最后一次有元素相同的时候的j的值
35                     }
36                 }
37             }
38             if(key == i)ans --;//如果“b”序列最后一次和“a”序列相同的时候是出现在“mid”的位置，长度-1
39         }
40         printf("%d
", ans);
41     }
42     return 0;
43 }