Mengxin summary of LIS (longest ascending subsequence) topics

LIS（ Longest ascending subsequence ） Summary of topics

kuangbin Take you to fly topic 12 Basics DP1 Answer key + summary A big guy sorted it out
Mengxin is writing records again
LIS It's a very important DP application ~ It can be used in many questions , Many problems can be directly or indirectly transformed into LIS The solution of the problem .
As far as possible Use both nlogn The algorithm of ( A monotonous queue ) Write ~ however Does not mean that you do not use n2 Algorithm La （ The data is very small , Not just asking LIS The length of , There are other requirements （ Such as output path , Make a peace, etc , use n2 It's easy ）, consider n2 Algorithm ）
Put a template nlogn：

#include<cstdio>
#include<algorithm>
using namespace std;

int t,n,len,book[40005],ans[40005];
int binary_search(int x){
    
	int left = 1, right = len, mid;
	while(left <= right){
    			// If there is an equal sign here , below right = mid - 1, Draw your own picture  
		mid = (right + left) / 2;
		if(ans[mid] >= x)	right = mid - 1;
		else	left = mid + 1;
	}
	return left;
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		for(int i = 1; i <= n; ++i)
			scanf("%d",&book[i]);
		ans[1] = book[1], len = 1;
		for(int i = 2; i <= n; ++i){
    
			if(book[i] > ans[len])	ans[++len] = book[i];
			else{
    
				// int pos = binary_search(book[i]);  Easy to mess up , Call library function 
				*lower_bound(ans + 1, ans + 1 + len, book[i]) = book[i]; 
				//ans[pos] = book[i];
			}
		}
		printf("%d\n",len);
	}
	return 0;
} 

The binary function can be written by itself （ Like above ）, You can also call library functions lower_bound(),upper_bound(); Which one to use depends on whether it is strictly monotonic or not strictly monotonic （ namely ： Can there be an equal sign ）. Similarly, the longest descent subsequence can also be found / Do not increment subsequence , You can choose to overload the comparator in the function (greater<…>), You can also choose to count backwards .

Put one more n2 Template of algorithm 8！

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1005; 
int n,book[maxn],dp[maxn];

int main(){
    
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)
		scanf("%d",&book[i]);
	int res = 0;
	for(int i = 1; i <= n; ++i){
    
		dp[i] = 1;
		for(int j = 1; j < i; ++j){
    
			if(book[j] < book[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		res = max(res, dp[i]);
	}
	printf("%d",res);
	return 0;
}

Put one more nlogn Template of output path 8！（G topic ）

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1005;

int cnt,po,n,ans[maxn],pos[maxn],list[maxn],book[maxn];
int main(){
    
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&book[i]);
    ans[++cnt] = book[1], pos[++po] = 1;
    for(int i = 2;i <= n;i++){
    
        if(ans[cnt] < book[i]){
    
            ans[++cnt] = book[i];
            pos[++po] = cnt;	// Used to record from a[i] in 1 To n In each position dp Position in  
        }else{
                   
            int tmp = lower_bound(ans + 1, ans + 1 + cnt,book[i]) - ans;
            ans[tmp] = book[i];
            pos[++po] = tmp;
        }
    }
    int t = cnt;
    for(int i = n;i >= 1;i--){
    
        if(pos[i] == t)
            list[t--] = book[i];
        if (t<1) break; 
    }
    for(int i = 1;i <= cnt;i++) 
    	printf("%d\n",list[i]);
    return 0;
}

A.POJ2533(Longest Ordered Subsequence）
LIS The template question of . Strictly monotonically increasing .

#include<cstdio>
#include<algorithm>
using namespace std;

int n,book[1005],ans[1005],cnt;

int main(){
    
	while(~scanf("%d",&n)){
    
		for(int i = 1; i <= n; ++i)
			scanf("%d",&book[i]);
		ans[1] = book[1], cnt = 1;
		for(int i = 2; i <= n; ++i){
    
			if(book[i] > ans[cnt])	ans[++cnt] = book[i];
			else	*lower_bound(ans + 1, ans + 1 + cnt, book[i]) = book[i];
		}
		printf("%d\n",cnt);
	}
	return 0;
} 

B.POJ 1836 Alignment / Luogu P1091 Chorus formation
tips: Find the least number to delete , Make any number taken from the sequence h[i], Yes h[1] ~ h[i] Strict single increase , or h[i] ~ h[n] Strictly reduce .（ The shape of a mountain ）.
Ideas ： positive / Reverse the search LIS
nlogn In the monotonic queue of, the length is len Of LIS What is the end of , instead of LIS In itself , Nor is it when you choose this position LIS Maximum length of . So you need to use an array d To record when the current position is selected ,LIS The maximum of .
After processing , It's on the second floor for Loop enumeration d Array .
P.S. These two questions are almost identical , Data types are different .
POJ1836:

#include<cstdio>
#include<algorithm>
using namespace std;

int n,cnt1,cnt2,d1[1005],d2[1005];
double ans1[1005],ans2[1005],book[1005];

int main(){
    
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)
		scanf("%lf",&book[i]);
	ans1[1] = book[1], cnt1 = 1, d1[1] = 1;
	for(int i = 2; i <= n; ++i){
    
		if(book[i] > ans1[cnt1])	ans1[++cnt1] = book[i], d1[i] = cnt1;
		else	*lower_bound(ans1 + 1, ans1 + 1 + cnt1, book[i]) = book[i], d1[i] = cnt1;
	}
	ans2[1] = book[n], cnt2 = 1, d2[n] = 1;
	for(int i = n - 1; i >= 1; --i){
    
		if(book[i] > ans2[cnt2])	ans2[++cnt2] = book[i], d2[i] = cnt2;
		else	*lower_bound(ans2 + 1, ans2 + 1 + cnt2, book[i]) = book[i], d2[i] = cnt2;
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			cnt = max(cnt, d1[i] + d2[j]);
	printf("%d",n - cnt);
	return 0;
}

Chorus formation ：

#include<cstdio>
#include<algorithm>
using namespace std;

int n,cnt1,cnt2,d1[1005],d2[1005];
int ans1[1005],ans2[1005],book[1005];

int main(){
    
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)
		scanf("%d",&book[i]);
	ans1[1] = book[1], cnt1 = 1, d1[1] = 1;
	for(int i = 2; i <= n; ++i){
    
		if(book[i] > ans1[cnt1])	ans1[++cnt1] = book[i], d1[i] = cnt1;
		else	*lower_bound(ans1 + 1, ans1 + 1 + cnt1, book[i]) = book[i], d1[i] = cnt1;
	}
	ans2[1] = book[n], cnt2 = 1, d2[n] = 1;
	for(int i = n - 1; i >= 1; --i){
    
		if(book[i] > ans2[cnt2])	ans2[++cnt2] = book[i], d2[i] = cnt2;
		else	*lower_bound(ans2 + 1, ans2 + 1 + cnt2, book[i]) = book[i], d2[i] = cnt2;
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			cnt = max(cnt, d1[i] + d2[j]);
	printf("%d",n - cnt);
	return 0;
}

C.Wooden Sticks POJ - 1065 / Luogu P1233 Stick processing
The two questions are almost identical ~ The key is how to transform the problem .
The length of the stick 、 Width has two properties , In fact, it defines a partial order relation .（ This problem can also be transformed into a rectangular complete coverage problem ）~
obviously , First sort according to the length from high to low , If the length is the same , Then sort according to the width from high to low . If it is in the same preparation cycle , The front stick must be processed before the back stick .
such , This problem turns into n In number , Find the minimum number of non descending subsequences .
according to dilworth Theorem , The minimum number of non ascending subsequences is equal to the length of the longest ascending subsequence .
Add a theorem of Discrete Mathematics ：Dilworth（bu shuo ren hua Dilworth ） Theorem ： The least anti chain partition fraction of a poset is equal to the length of the longest chain （？？）. That is to say ： ** The number of non ascending subsequences is equal to the length of the longest ascending subsequence . vice versa .** You can see below D topic .
The problem is reduced to seeking n The largest ascending subsequence of the number .

#include<bits/stdc++.h>
using namespace std;
struct wood{
    
	int a,b;
}stick[10005];
int cmp(wood w1, wood w2){
    
	return (w1.a != w2.a) ? w1.a > w2.a : w1.b > w2.b ;
}
int n,ans[10005],cnt,t;
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		for(int i = 1; i <= n; ++i)
			scanf("%d%d",&stick[i].a,&stick[i].b);
		sort(stick + 1, stick + 1 + n, cmp);
		ans[1] = stick[1].b, cnt = 1;
		for(int i = 1; i <= n; ++i){
    
			if(stick[i].b > ans[cnt])	ans[++cnt] = stick[i].b;
			else	*lower_bound(ans + 1, ans + 1 + cnt, stick[i].b) = stick[i].b;
		}
		printf("%d\n",cnt);
	}
	return 0;
}

D. Luogu P1020 Missile intercept / At least intercept the system HDU - 1257
tips： Is still d-w The application of the theorem . Classic questions .
“ The second number indicates the minimum number of such missile interception systems to be equipped if all missiles are to be intercepted ” Is to find the total number of non descending subsequences -> To find the length of the longest ascending subsequence .
it is to be noted that upper/lower The choice of ！！！！
Missile intercept ：

#include<bits/stdc++.h>
using namespace std;

int n,book[100005], ans[100005],cnt,num,cnt2;

int main(){
    
	while(~scanf("%d",&book[++num])); num--;
	ans[++cnt] = book[1];
	for(int i = 2; i <= num; ++i){
    
		if(ans[cnt] >= book[i])	ans[++cnt] = book[i];
		else	*upper_bound(ans + 1, ans + 1 + cnt, book[i], greater<int>()) = book[i];
	}
	ans[++cnt2] = book[1];
	for(int i = 2; i <= num; ++i){
    
		if(ans[cnt2] < book[i])	ans[++cnt2] = book[i];
		else	*lower_bound(ans + 1, ans + 1 + cnt2, book[i]) = book[i];
	}
	printf("%d\n%d",cnt,cnt2);
	return 0;
} 

At least intercept the system

#include<cstdio>
#include<algorithm>
using namespace std;

int book[10005],n,cnt,ans[10005];
int main(){
    
	while(~scanf("%d",&n)){
    
		for(int i = 1; i <= n; ++i)
			scanf("%d",&book[i]);
		cnt = 0, ans[++cnt] = book[1];
		for(int i = 2; i <= n; ++i){
    
			if(book[i] > ans[cnt])	ans[++cnt] = book[i];
			else	*lower_bound(ans + 1, ans + 1 + cnt, book[i]) = book[i];
		}
		printf("%d\n",cnt);
	}
	return 0;
}

A sequence of numbers is divided into least Of Longest non ascending subsequence Of number It is equal to the longest of this series rising Of subsequences length .

Why? ？ There is a simple way to understand ：

For each element in the longest ascending subsequence , Two cannot be divided into a group , So the length of this sequence （length） How much? , At least how many non ascending subsequences should be divided .

Reduction to absurdity , If divided length A non ascending subsequence cannot meet the meaning of the question . Then there must be another element outside the sequence and the elements of the sequence cannot be divided into a group , And the condition that two cannot be divided into a group is that this element and the elements of the sequence form an ascending subsequence . therefore , This “ Longest ascending subsequence ” The length of is not the longest , contradiction , That is to say, the number of the longest non ascending subsequence of a sequence is equal to the length of the longest ascending subsequence of the sequence .

E.Dining Cows POJ - 3671
tips: Give you a string of only 1,2 The number of , Let you change the least number of times , Make this sequence non decreasing . The idea is to find the longest non decreasing subsequence length , Just change the rest ~

#include<cstdio>
#include<algorithm>
using namespace std;

int n,book[30005],ans[30005],cnt;

int main(){
    
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)
		scanf("%d",&book[i]);
	ans[++cnt] = book[1];
	for(int i = 2; i <= n; ++i){
    
		if(ans[cnt] <= book[i])	ans[++cnt] = book[i];
		else	*upper_bound(ans + 1, ans + 1 + cnt, book[i]) = book[i];
	}
	printf("%d",n - cnt);
	return 0;
}

F.Super Jumping! Jumping! Jumping! HDU - 1087
tips: requirement The longest The maximum sum of ascending subsequences （ Note that it is not necessarily the longest ascending subsequence ！ Such as this group of data ： 1 2 9 3 4 The answer is 12, instead of 10）
This kind of question is still used n2 Algorithm 8！ Change my dp The meaning of array .（ original dp[i] It means the longest LIS The length of , Now it becomes the maximum sum of the ascending subsequence so far ~）
The array name is girl It's because the original question is about strategies, miss

#include<cstdio>
#include<algorithm>
using namespace std;

int n,girl[1005],dp[1005],ans;

int main(){
    
	while(~scanf("%d",&n) && n){
    
		for(int i = 1; i <= n; ++i){
    
			scanf("%d",&girl[i]);
			dp[i] = girl[i];
		}
		ans = 0;
		for(int i = 1; i <= n; ++i){
    
			for(int j = 1; j < i; ++j){
    
				if(girl[i] > girl[j])
					dp[i] = max(dp[i], dp[j] + girl[i]);
			}
			ans = max(ans, dp[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

G.FatMouse’s Speed HDU - 1160（ A very important question ！ The output path ）
tips: Find the longest sequence , bring ： The weight of the mouse increases strictly , And the speed decreases strictly ~
Use after sorting LIS do . however ！！ This question needs The output path ！
Learn about monotonous queues nlogn Method of output path ： Put a big guy's explanation 8
LIS nlogn Optimization and path output
Path output —— Output in reverse order （ans The length of is the length of the longest subsequence ）, from cnt To 1,t–, Find the first pos[i]=t Where the output .( Here must be the first , Otherwise, it may not be LIS 了 （ Traverse backwards , first pos[i]=t The position must be the smallest （ This is also ans The meaning of array ））)
use pos Record location , use list Record path ~ Only one path can be output here （ Generally, this kind of question will special judge）
See the template above ~

This question only needs to be sorted by weight gain , The descending order of the same weight and speed can be transformed into the longest descending subsequence about speed （ heavy load lower_bound function ）.
Pay attention to your weight Strictly increasing It's the premise , Same weight but decreasing speed Can it be put together to form LIS Of ！

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;

struct mouse{
    
	int wei,speed, id;
}book[1005];
int n,speed,wei,cnt,ans[1005],list[1005],pos[1005],po,lastwei;
int cmp(mouse m1, mouse m2){
    
	return (m1.wei != m2.wei) ? m1.wei < m2.wei : m1.speed > m2.speed;
}
int main(){
    
	while(~scanf("%d%d",&wei,&speed))	book[++n].speed = speed, book[n].wei = wei, book[n].id = n;
	sort(book + 1, book + n + 1, cmp);	
/* for(int i = 1; i <= n; ++i) printf("%d %d %d\n",book[i].wei,book[i].speed,book[i].id);*/
	ans[++cnt] = book[1].speed, pos[++po] = 1, lastwei = book[1].wei;
	for(int i = 2; i <= n; ++i){
    
		//if(lastwei == book[i].wei) continue;  You can't write like this 
		if(ans[cnt] > book[i].speed &&  book[i].wei > lastwei)	ans[++cnt] = book[i].speed, pos[++po] = cnt;
		else {
    
			int temp = lower_bound(ans + 1, ans + 1 + cnt, book[i].speed, greater<int>()) - ans;
			ans[temp] = book[i].speed;
			pos[++po] = temp;
		}	 
		lastwei = book[i].wei;
	}
	int t = cnt;
    for(int i = n; i >= 1;i--){
    
        if(pos[i] == t){
    
            list[t--] = book[i].id;
        }
        if (t < 1) break; 
    }
	printf("%d\n",cnt);
	for(int i = 1;i <= cnt;i++) printf("%d\n",list[i]);
	return 0;
}

But this question , still n2 The algorithm is more convenient to find the path ~
n2 error Code ：

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;

struct mouse{
    
	int wei,speed, id;
}book[1005];
int n,speed,wei,ans,dp[1005];
int cmp(mouse m1, mouse m2){
    
	return (m1.wei != m2.wei) ? m1.wei < m2.wei : m1.speed > m2.speed;
}

int main(){
    
	while(~scanf("%d%d",&wei,&speed))	book[++n].speed = speed, book[n].wei = wei, book[n].id = n;
	sort(book + 1, book + 1 + n, cmp);
	for(int i = 1; i <= n; ++i){
    
		dp[i] = 1;
		for(int j = 1; j < i; ++j)
			if(book[j].wei < book[i].wei && book[j].speed > book[i].speed)	dp[i] = max(dp[i], dp[j] + 1);
		ans = max(ans, dp[i]);
	}
	printf("%d\n",ans);
	int idx = 1;
	for(int i = 1; i <= n; ++i){
    
		if(dp[i] == idx++)
			printf("%d\n",book[i].id);
	}
	return 0;
}

n2 Correct code ：

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;

struct mouse{
    
	int wei,speed, id;
}book[1005];
int n,speed,wei,ans,dp[1005];
int cmp(mouse m1, mouse m2){
    
	return (m1.wei != m2.wei) ? m1.wei < m2.wei : m1.speed > m2.speed;
}

int main(){
    
	while(~scanf("%d%d",&wei,&speed))	book[++n].speed = speed, book[n].wei = wei, book[n].id = n;
	sort(book + 1, book + 1 + n, cmp);
	for(int i = n; i >= 1; --i){
    
		dp[i] = 1;
		for(int j = i + 1; j <= n; ++j)
			if(book[j].wei > book[i].wei && book[j].speed < book[i].speed)	dp[i] = max(dp[i], dp[j] + 1);
		ans = max(ans, dp[i]);
	}
	printf("%d\n",ans);
	for(int i = 1; i <= n; ++i){
    
		if(dp[i] == ans){
    
			ans--;
			printf("%d\n",book[i].id);
		}
	}
	return 0;
}

Want to direct the output path , It must be upside down dp~（ This is also the reason for the first code error ）
Take a chestnut ：1 2 6 3 4
positive DP ： 1 2 3 3 4
positive DP+ The path to output is 1 2 6 4, Obviously not LIS.
sleep DP： 4 3 1 2 1
reverse DP+ The path to output is 1 2 3 4, Is the answer you want
So the strategy is ： reverse DP+ Forward output

To be continued ing……