8.3 LIS LCS LCIS（完结了==！）-白红宇

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

阅读量：5010 次

发布时间：2019-06-12

本文共 8515 字，大约阅读时间需要 28 分钟。

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

地址

密码 acmore

Problem A

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

解题方法见

下面随便贴上两段代码

1 #include 
     
       2 #include 
      
        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

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

1 #include 
      
        2 #include 
       
         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

View Code

Problem B

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

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

2460 KB 109 ms

1 #include 
     
       2 #include 
      
        3 #include 
       
         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]
        
         d[len])30        {31            d[++len] = A[i];32        }33        else34        {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
         
          =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

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

276 KB 375 ms

1 #include 
     
       2 #include 
      
        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

Problem C

这道题我用的方法是，直接将各种变换存放在一个数组里面，并记录每个字母可以变化为其他字母的个数，这样在对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 
     
       2 #include 
      
        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

Problem D

题解见

Problem E

题目的意思是说一些娃娃有大小不同的很多个，小的可以放进大的里面，前提条件是它的宽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 
     
       2 #include 
      
        3 #include 
       
         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

Problem F

裸的LCIS，百度之或见

1 #include 
     
       2 #include 
      
        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\n", ans);26         if(T)printf("\n");27     }28     return 0;29 }

Problem G

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

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

由于是要求两端相等但也要使得序列升序且最长，那我们就枚举中点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~mid10     {11         int Maxx = 0;12         for(int j=N;j>=mid;j--)//右边区间从N~mid13         {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次,所以-123                 }24             }25         }26     }27     Max = MAX(Max, ans);//找出最大的解28 }29 printf("%d\n", 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 
     
       2 #include 
      
        3 #include 
       
         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”的位置，长度-139         }40         printf("%d\n", ans);41     }42     return 0;43 }