专题2:最长上升子序列LIS

    A HDU 1025 Constructing Roads In JGShining's Kingdom
    B POJ 3903 Stock Exchange
    C OpenJ_Bailian 1065 Wooden Sticks
    D OpenJ_Bailian 1631 Bridging signals
    E OpenJ_Bailian 1952 BUY LOW, BUY LOWER
    F OpenJ_Bailian 2533 Longest Ordered Subsequence
    G OpenJ_Bailian 1692 Crossed Matchings
    H HDU 2881 Jack's struggle

点击题号进入题目链接

-----

A hdu 1025

题意:

　　两条平行直线,每条线上n个点,从1-n顺序安放

　　每个点想与另一个直线上的一个目标点连线,

　　每个点的匹配对象不会重复,不会多余

　　要求匹配过程中不能出现交叉的连线

　　求最大匹配数量

分析:

　　LIS的简单转化

　　由于不能交叉,也没有重复的匹配点

　　因此,记子序列{Ai}为最终选出的所有进行匹配的点中,第i个点所对应的目标点编号

　　显然,当Ai的值为j时,后续Ai+1....都只能大于j

　　简单来说:Ai==j 时 Ai+1>j,转化一下就是 Ai<AI+1.......

　　也就是一个单调上升子序列

　　答案求的最大匹配数量,也就是最长上升子序列的长度了 

　　注意,这里用朴素的算法无法达到要求的复杂度,需要进行二分优化

 1 /**********************
 2 *@Name:
 3 *
 4 *@Author: Nervending
 5 *@Describtion:
 6 *@DateTime:
 7 ***********************/
 8 #include <bits/stdc++.h>
 9 using namespace std;
10 const int maxn=1e5+10;
11 const int INF=0x3f3f3f3f;
12 int road[maxn];
13 int dp[maxn];
14 const int inf = 0x7fffffff;
15 int main(){
16     int c=1;
17     int n;
18     while((scanf("%d",&n))!=EOF) {
19         for(int i=0; i<=n; i++) {
20             dp[i]=inf;
21         }
22         for(int i=0; i<n; i++) {
23             int tmp1,tmp2;
24             scanf("%d%d",&tmp1,&tmp2);
25             road[tmp1]=tmp2;
26         }
27         int len=0;
28         for(int i=1; i<=n; i++) {
29             *lower_bound(dp,dp+n,road[i])=road[i];
30         }
31         len = lower_bound(dp,dp+n,inf)-dp;
32         if(len==1) {
33             cout<<"Case "<<c++<<":"<<endl;
34             cout<<"My king, at most 1 road can be built."<<endl;
35         } else {
36             cout<<"Case "<<c++<<":"<<endl;
37             cout<<"My king, at most "<<len<<" roads can be built."<<endl;
38         }
39         cout<<endl;
40     }
41     return 0;
42 }
View Code

------------

B POJ 3903

 题意:

　　给一个数列,求他的最大上升子序列

分析:

　　二分优化LIS的裸题

　　直接看代码

 1 /**********************
 2 *@Name:
 3 *
 4 *@Author: Nervending
 5 *@Describtion:
 6 *@DateTime:
 7 ***********************/
 8 #include <iostream>
 9 #include <algorithm>
10 #include <string.h> 
11 #include <cstdio>
12 using namespace std;
13 const int maxn=1e6+10;
14 const int INF=0x3f3f3f3f;
15 int num[maxn];
16 int dp[maxn];
17 int n;
18 int main(){
19 //    freopen("in.txt","r",stdin);
20 //    freopen("out.txt","w",stdout);
21     while((scanf("%d",&n))!=EOF) {
22         memset(dp,INF,sizeof dp); 
23         for(int i=0; i<n; i++) {
24             scanf("%d",&num[i]);
25         }
26         int len=0;
27         for(int i=0; i<n; i++) {
28             *lower_bound(dp,dp+n,num[i])=num[i];
29         }
30         len = lower_bound(dp,dp+n,INF)-dp;
31         cout<<len<<endl;
32     }
33     return 0;
34 }
View Code

 ---------

C POJ 1065

题意:

　　给一些物品,有重量和大小2个性质,要对它们进行处理

　　处理第一个物品,需要1分钟,

　　对于后续的物品,如果重量和大小都大于上一个物品,则不需要时间

　　否则需要1分钟

　　对于每组物品,求出最小的处理时间

分析:

　　单看一种属性,是单纯的LIS而已,但出现了2个属性,就需要转化了

　　首先,对于重量和大小可以分开处理

　　把所有的物品按照大小排序,大小一样就按照重量排序

　　这样,遍历过程中所有物品的大小就一定是递增的,其实就只需要对重量找LIS就行

　　每次找LIS,处理掉,然后再找下一个.期间使用二分优化,直到结束,最后答案就是LIS的数量

　　但上面的做法太麻烦,实际上有更好的方法

　　对于每次取LIS,如果是第i个,则前面所有重量小于Wi的物品都会被处理,

　　如果多个一样重量则减少一个,是哪个不影响答案

　　这样,我们会发现,最重的物品一定会是某一个LIS的最后一个

　　而每次的LIS终点,之后也一定不存在比它更重的物品了,而之前可能存在比它重的

　　经过简单的推广思考,实际上只要能找到所有的LIS终点,显然这些LIS的处理顺序是无所谓的

　　而手推几组数据,可以发现所有LIS的终点,其最后一个物品的重量一定是递减的

　　简单来说,如果不是递减的,则当前的LIS就一定不是LIS,至少可以再加长一个

　　转化到最后,可以发现,LIS的最后一个物品的质量,组成了一个最长的单调递减序列

　　而这个序列的长度,也就是LIS的个数,也就是答案

　　所以最佳的解法是:

　　　　对于所有的物品,按照大小排序,一致就按照重量排序,最后再根据重量找出一个最长单调递减子序列,长度即为答案

 在第二种方法+二分优化,最终速度非常快

 1 /**********************
 2 *@Name:
 3 *
 4 *@Author: Nervending
 5 *@Describtion:
 6 *@DateTime:
 7 ***********************/
 8 #include <bits/stdc++.h>
 9 #define oj
10 using namespace std;
11 const int maxn=1e6+10;
12 const int INF=0x3f3f3f3f;
13 typedef pair<int,int> p;
14 p num[maxn];
15 int dp[maxn];
16 int n;
17 int vis[maxn];
18 int main(){
19 #ifndef oj
20     freopen("in.txt","r",stdin);
21     freopen("out.txt","w",stdout);
22 #endif
23     int casn;
24     scanf("%d",&casn);
25     while(casn--) {
26         memset(vis,false,sizeof vis);    
27         memset(dp,-1,sizeof dp);
28         scanf("%d",&n);
29         for(int i=0; i<n; i++) {
30             scanf("%d%d",&num[i].first,&num[i].second);
31         }
32         sort(num,num+n);
33         for(int i=0; i<n; i++) {
34             *lower_bound(dp,dp+n,num[i].second,greater<int>())=num[i].second;
35         }
36          
37         int ans = lower_bound(dp,dp+n,-1,greater<int>())-dp;
38         printf("%d
",ans);
39     }
40 #ifndef oj
41     fclose(stdin);
42   fclose(stdout);
43     system("out.txt");
44 #endif
45     return 0;
46 }
View Code

 ----

D poj 1631

题意:

　　和A差不多

分析:

　　和A差不多,需要使用二分优化

 1 /**********************
 2 *@Name:
 3 *
 4 *@Author: Nervending
 5 *@Describtion:
 6 *@DateTime:
 7 ***********************/
 8 #include <bits/stdc++.h>
 9 
10 using namespace std;
11 const int maxn=1e6+10;
12 const int INF=0x3f3f3f3f;
13 int num[maxn];
14 int dp[maxn];
15 int n;
16 int vis[maxn];
17 int main(){
18 //#define test
19 #ifdef test
20     freopen("in.txt","r",stdin);
21     freopen("out.txt","w",stdout);
22 #endif
23 
24     int casn;
25     scanf("%d",&casn);
26     while(casn--) {
27         memset(vis,false,sizeof vis);    
28         memset(dp,INF,sizeof dp);
29         scanf("%d",&n);
30         for(int i=0;i<n;i++){
31             scanf("%d",&num[i]);
32         }
33         for(int i=0;i<n;i++){
34             *lower_bound(dp,dp+n,num[i])=num[i];
35         }
36         int ans=lower_bound(dp,dp+n,INF)-dp;
37         printf("%d
",ans);
38     }
39     #ifdef test
40     fclose(stdin);
41   fclose(stdout);
42     system("out.txt");
43     #endif
44     return 0;
45 }
View Code

-----

 ...懒得写了,明天更新

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/nervendnig/p/8412005.html