当前位置：网站首页>LIS (longest ascending subsequence) problem that can be understood [easy to understand]
LIS (longest ascending subsequence) problem that can be understood [easy to understand]
2022-07-01 21:55:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm your friend, Quan Jun .
LIS Introduction to the problem ：
First of all, what is LIS problem ：
There's a long one for n Sequence of numbers a0, a1, ……, a(n-1). Request the length of the longest ascending subsequence in this sequence . Ascending subsequence refers to any i<j All satisfied with ai<aj The subsequence , This problem is called the longest ascending subsequence （LIS,Longest Increasing Subsequence） The famous problem of .
Take a chestnut ： Give you a sequence of （1,5 ,2,6,9,10,3,15）, Then its longest ascending subsequence is ：（1,2,6,9,10,15）
This question uses DP The idea of is easy to solve , Now let's talk about DP（ Dynamic programming ） Thought .
DP brief introduction （ The boss can ignore the content in this title ）
Don't worry for a moment Meeting ！ detailed ！！！ To talk about LIS Problem and its optimization method , For better understanding LIS problem , So let's talk first DP, If you have done some DP You can ignore this introduction DP Explanation , If you are just beginning to contact the suggestion, read it patiently , I believe there will be a great harvest . One 、DP thought ： 1、 Decompose a big problem into subproblems one by one . 2、 If we get the solutions of these subproblems , And then after some treatment , We can get the solution of the original problem . 3、 If these subproblems have the same structure as the original problem , That is, small problems can continue to decompose . 4、 In this way, the big problems are always separated , The scale of the problem is decreasing , Until the subproblem is too small , You'll end up with the youngest problem . 5、 The solution to the minimal problem is obvious , So it recurs back , We can get the solution of the original problem .
Two 、DP The concrete realization of ： 1、 To analyze problems , Get the state transition equation （ Recurrence equation ）. 2、 According to the state transition equation , Start with the atomic problem , Constantly solve upward , Know to get the solution of the original problem . 3、 In the process of constantly solving recursive equations , It's actually a form filling process .
What I just said is hard for me to understand , Too abstract. , For example 2 A chestnut , Let's have a better understanding of DP Thought .
The first chestnut ：//https://vjudge.net/contest/239734#problem/B
Problem description ： Here you are N（N Is odd && 1<=N<=999999） Sequence of Numbers , And guarantee this N One of the numbers M The number of >= （N + 1)/2 , Let you find this number M.
Sample Input: 5 1 3 2 3 3 Sample Output: 3
according to DP Thought , Divide this big problem into several small problems first . So when N by N when , There are at least （N + 1）/ 2 individual M, The other number is left to him ; …… Then when N by 5 It's time , According to the meaning of the title, there must be at least 3 individual M, The other two numbers are left alone ; When N by 3 When , According to the question , There must be two numbers M, The other number is left alone ; First See when N by 1 When , Then this number must be M. So we can delete two different numbers in this sequence （ Delete as long as there are two different numbers ）, The last thing left must be M; Take a chestnut ： intput: 9 3 6 9 3 3 3 8 6 3 loc ： 1 2 3 4 5 6 7 8 9 1、2 Position delete 3、4 Position delete 6、7 Position delete 8、9 Position delete ,, And then there were one 5 Location , that 5 Positional 3 That's what I'm looking for M .
AC Code ：
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int arr[1000006];
int dp[1000006];
int main()
{
int n;
while(scanf("%d", &n) != EOF){
memset(arr, 0, sizeof(arr));
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
int i = 0, j = 1;
while(j < n){
if(dp[i] == 1){
while(dp[i] == 1)
i++;
}
if(arr[i] != arr[j]){
i++;
dp[j++] = 1;
}
else if(arr[i] == arr[j]){
while(arr[i] == arr[j])
j++;
}
}
while(dp[i] == 1) i++;
printf("%d\n", arr[i]);
}
return 0;
}Another chestnut ：//http://acm.hdu.edu.cn/showproblem.php?pid=2084
This problem is a number tower problem ： There are several towers as shown below , It is required to go from the top to the bottom , If each step can only go to the adjacent node , What is the maximum sum of the number of nodes passing by ？
Input： The input data first includes an integer C, Indicates the number of test instances , The first line of each test instance is an integer N(1 <= N <= 100), Indicates the height of the tower , Next use N A line number means a tower , Among them the first i There's a i It's an integer , And all integers are in intervals [0,99] Inside . Output： For each test case , The maximum sum of possible outputs , The output of each instance takes up one line . Sample Input： 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output： 30
First analyze this topic , Leftmost left / The most right The size of is determined by the upper one , The middle one is decided by the two above . set up i Is the number of layers ,DP thought , Turn a big problem into a sub problem , The big problem is to solve the maximum value of the addition from the top to the bottom , Then the maximum value must be on the last line , Want to find the maximum value of the last line , You have to make sure n – 1 Line inclusion n – 1 Line and its previous maximum , Push it up like this , There is When i == 3 when The third line , In order to ensure as large as possible , Then the middle number has to be chosen , Because the middle can be added to the upper left corner or the upper right corner , Then choose the biggest one and add it to yourself ; When i == 2 when Add the top number to each number in the second line ; When i by 1 When , The biggest thing is himself ,
By analogy , Then the biggest one along the way must be in the last line , Traverse it and get the answer . This tower can be stored in an array , If you expand this array , This question will be more concise ：
（ notes ： The above picture is wrong ,9 Should be changed to 10）
In this way, no matter which row or column , We just need to see which is bigger on the left and right , Just add it to itself , Only in this way can we ensure the journey , When we get to the last line , The last line must have a maximum . From this, we can find the state transition equation （ That is, recursive equation ） dp[ i ][ j ] = max(dp[ i – 1 ][ j ] , dp[ i – 1 ][ j – 1 ]) + arr[ i ][ j ];
AC Code ：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[105][105], arr[105][105], n, c, MAX;
int main()
{
scanf("%d", &c);
while(c--){
MAX = -1;
memset(dp, 0, sizeof(dp));
memset(arr, 0, sizeof(arr));
scanf("%d", &n);
arr[0][0] = arr[0][1] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
scanf("%d", &arr[i][j]);
arr[i][0] = 0;
arr[i][i + 1] = 0;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i][j] = arr[i][j];
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
}
}
for(int i = 1; i <= n; i++)
MAX = max(MAX, dp[n][i]);
printf("%d\n", MAX);
}
}After you understand this problem, you can try to rely on yourself AC A question , This topic is basically the same as this type , It's just a little bit harder than this , But it can deepen understanding . Address ：https://vjudge.net/contest/239734#problem/G
LIS Detailed explanation ：
First, let's explain his recursive relation ： Definition dp[ i ] by ： With ai Is the length of the longest ascending subsequence at the end . that dp[ i ] What does it contain ？
situation 1`: Only include itself , That is to say, all the elements in front of it are bigger than him ; Take a chestnut ： A sequence （7, 9, 6, 10, 7, 1, 3） Respectively （a1, a2, a3, a4, a5, a6, a7） that dp[ 6 ] == 1;
situation 2`： In order to ensure that the ascending subsequence is as long as possible , Then there is dp[ i ] As big as possible , But promise again dp[ i ] On the largest possible basis , It must also meet the rise of the sequence ; So dp[ i ] = max ( 1 , dp[ j ] + 1 ) { j < i && aj < ai } . there 1 Is that when ai When the previous numbers are bigger than him , He himself is a subsequence ;dp[ j ] + 1 refer to ： When the first i There is one in front of the number The first j The number satisfies aj < ai also j < i At this time, it means ai Elements can be inherited in aj After the element, increase the length of the subsequence as much as possible .
take j from 1 Traversing i – 1 , In between , Find the largest possible dp[ i ] That is, the length of the longest ascending subsequence ( At the prompt dp[n] Not necessarily the longest subsequence ,n Is the number of numbers in the sequence , For example, the sequence [ 2, 3, 4, 5, 1 ],dp[5] = 1( By subsequence [1] constitute ), However dp[4] = 4( By subsequence [2,3,4,5] constitute ) )
The above is still a little general , Then take another chestnut ： Still use the sequence just now ：（7, 9, 6, 10, 7, 1, 3） Respectively （a1, a2, a3, a4, a5, a6, a7）
In the beginning a1 = 7, Make dp[ 1 ] = 1; Then look at the next element a2 = 9, Make dp[ 2 ] = 1, Then it needs to be checked i Whether there is one smaller than him in front because a1 < a2 and dp[ 1 ] + 1 > dp[ 2 ], therefore dp[ 2 ] = dp[ 1 ] + 1 == 2; Then look at the next element a3 = 6, Make dp[ 3 ] = 1, Then you need to check the previous elements a1 And a2 Is there anyone smaller than him , There is no such thing as , Spicy? up to now , The subsequence is himself . Then look at the next element a4 = 10; Make dp[ 4 ] = 1; Then you need to check the previous elements in turn a1 And a2 And a3 Is there anyone smaller than him , Take a look a1 Smaller than it , And ,dp[ 1 ] + 1 > dp[ 4 ] So dp[ 4 ] = dp[ 1 ] + 1 == 2, That at this time a1 And a4 Can form a length of 2 The ascending subsequence of , Let's see if we can form longer subsequences , So let's take a look again a2 , a2 < a4 And dp[ 2 ] + 1 == 3 > dp[ 4 ] == 2 So dp[ 4 ] = dp[ 2 ] + 1 == 3, the a4 Undertake in a2 Later than in a1 Better after , Undertake in a2 The following sequence is ：a1 a2 a4 , Form a length of 3 The ascending subsequence of ; Then I'll see a3 , a3 < a4 But it's a pity d[ 3 ] + 1 == 2 < dp[ 4 ] == 3 , So you can't put a4 Add to a3 Behind . Then repeat the above process , Find the biggest dp [ i ] Then this number is the longest ascending subsequence . The code implementation is as follows ：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int arr[500], n, dp[500], ans = -1;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i]); // Not recommended for use cin cout When they execute, they have to analyze the data type first , Time ratio scanf printf Much more , Many questions are overtime because of this place , Lead to a penalty when the game
/* The core code for solving the number of the longest subsequence */
/* ********************************************** */
for(int i = 1; i <= n; i++){
dp[i] = 1; // initialization
for(int j = 1; j < i; j++){
if(arr[j] < arr[i]) // If the maximum descent subsequence is found, the opposite is true
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(dp[i], ans);
}
/* ********************************************** */
printf(" The number of longest subsequences is ： %d", ans);
return 0;
}
/*
Examples ：
7
7 9 6 10 7 1 3
The number of longest subsequences is ： 3
*/Is that over ？ If this is the end, it is not called detailed explanation ~ I'll talk slowly later , Its optimization and its method of marking paths .
Take a break , Now that you've learned, let's practice with a few templates ！（ There will be problem solving , Try it yourself first ！） https://vjudge.net/contest/218661#problem/A
Change the title to a template Title , Directly solve the longest ascending subsequence AC Code ：
//https://vjudge.net/contest/218661#problem/A
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int n, arr[1005], ans = -1, dp[1005];
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
for(int i = 1; i <=n; i++){
dp[i] = 1;
for(int j = 1; j < i; j++){
if(arr[j] < arr[i])
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(dp[i], ans);
}
printf("%d", ans);
return 0;
}https://vjudge.net/contest/239734#problem/E
This question is also a template question , Go straight to the code ：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1005], n, MAX;
int arr[1005];
int main()
{
while(scanf("%d", &n) != EOF){
if(n == 0) break;
MAX = -1;
for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
for(int i = 0; i < n; i++){
dp[i] = arr[i];
for(int j = 0 ; j < i; j++){
if(dp[i] < dp[j] + arr[i] && arr[i] > arr[j]){
dp[i] = dp[j] + arr[i];
}
MAX = max(dp[i], MAX);
}
}
printf("%d\n", MAX);
}
return 0;
}It's about finding out Vjudge Jumping again ... Another topic from Luogu , A few more may be added later Vjudge The subject of https://www.luogu.org/problemnew/show/P1091
Title Description
NNN Three students stand in a row , The music teacher is going to invite one of them ( N−KN-KN−K ) Three students came out , Make the rest KKK Three students form a chorus .
Chorus formation refers to such a formation ： set up K The students are numbered from left to right 1,2,…,K1,2,…,K1,2,…,K , Their heights are T1,T2,…,TKT_1,T_2,…,T_KT1,T2,…,TK , Then their height is satisfied T1<…<Ti>Ti+1>…>TK(1≤i≤K)T_1<…<T_i>T_{i+1}>…>T_K(1 \le i \le K)T1<…<Ti>Ti+1>…>TK(1≤i≤K) .
Your task is , All known N The height of a classmate , At least a few students are required for calculation , It can make the rest of the students form a chorus .
I / O format
Input format ：
Two lines in total .
The first line is an integer N(2≤N≤100)N(2 \le N \le 100)N(2≤N≤100) , Represents the total number of students .
The second line has nnn It's an integer , Separate... With spaces , The first iii It's an integer Ti(130≤Ti≤230)T_i(130 \le T_i \le 230)Ti(130≤Ti≤230) It's No iii The height of a classmate ( centimeter ).
Output format ：
An integer , At least a few students are required to stand out .
Sample input ： 8 186 186 150 200 160 130 197 220
Sample output ： 4
Answer key ： What he means is that he wants to keep students as much as possible . And the height is high in the middle and low on both sides , So if the tallest one is on the far left , Then it is enough to directly find the longest ascending sequence , If it's on the left , Then it is enough to find the longest ascending sequence directly from the right , But I'm not sure where the highest one is most suitable . Now the key As long as the highest one is determined , Find his longest ascending subsequence from the leftmost and his longest ascending and descending subsequence from the rightmost , This will ensure that the largest number of people remain , In other words, the number of people eliminated is the least . set up dp_1[ i ] To rise from the left i The highest rising number of students , dp_2[ n – i ] For descending from the right i The highest rising number of students , Sum up dp_3[ i ] = dp_1[ i ] + dp_2[ i ] So the biggest dp_3[ i ] , Take this as the end point, and the left side is lower , The right side is also lower , Then the maximum number of people left is dp_3[ i ] – 1 Subtract what he repeated twice chestnuts ：
Serial number i ： 1 2 3 4 5 6 7 8 height 186 186 150 200 160 130 197 220 Rise from the left dp_1[ i ] = 1 1 1 2 2 1 3 3 Go up and down from the right dp_2[ i ] = 4 4 2 3 2 1 1 1 The sum of the dp_3[ i ] = 5 5 3 5 4 2 4 4
In order to ensure as many as possible on the left in the middle , As many as possible on the right , So choose The sum of the dp_3[ i ] maximal Here is the When i == 1 || i == 2 || i == 4 When dp_3[ i ] – 1 == 4 （ Subtract what he repeated himself ）, So the answer is 8 – 4 == 4 , Because subtracting the most left , That's the answer ~ AC Code ：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int N, arr[105], dp[105] = {0}, dp2[105] = {0}, dp_all[105] = {0};
scanf("%d", &N);
for(int i = 0; i < N; i++) scanf("%d", &arr[i]);
for(int i = 0; i < N; i++){ // Find the longest ascending subsequence
dp[i] = 1;
for(int j = 0; j < i; j++){
if(arr[j] < arr[i] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
for(int i = N - 1; i >= 0; i--){ // Find the longest ascending subsequence from back to front
dp2[i] = 1;
for(int j = N - 1; j > i; j--){
if(arr[j] < arr[i] && dp2[i] < dp2[j] + 1)
dp2[i] = dp2[j] + 1;
}
}
int MAX = -1;
for(int i = 0; i < N; i++){
dp_all[i] = dp[i] + dp2[i];
MAX = max(MAX, dp_all[i]);
}
printf("%d", N - MAX + 1);
return 0;
}LIS Of nlogn The optimization of the ： LIS To put it bluntly, it is actually a greedy algorithm , For example, let's ask you to find a longest ascending subsequence to put , Let's walk together .
for instance （4, 2, 3, 1, 2,3,5） This sequence , Find his longest ascending subsequence , So look at , If the longest ascending sequence is found , Then according to greed , It should be most possible to make the elements of the sequence smaller as a whole , So that more elements can be added . Now open up a new array ,arr[ 10 ], { …….} –> This is his space , Now start to simulate the greedy algorithm to solve the longest ascending subsequence , The first number is 4, Add it first , So for { 4 } Let's look at the next number 2, It is better than 4 Small , So if he and 4 Whether replacement can make the current subsequence （ He is a subsequence of this element ） To become smaller , It's more convenient to add elements in the future ？ Yes . At the same time, it also ensures that the length of the sequence remains unchanged , Therefore, replacing a large number with a small one can make the whole sequence smaller on the premise that the sequence length remains unchanged , Easier to add elements . So now for { 2 } Let's look at his next element 3, He is better than 2 Big , So, add it behind him ,{ 2, 3} The next element is 1, It is better than 3 smaller , So, in order to ensure that the whole subsequence is as small as possible （ So that more elements can be added ）, Find the first number larger than him from the current sequence and replace it , Then it becomes { 1, 3}, continue .. The next number is 2, Then the sequence becomes { 1,2}, The next number is 3, Then the sequence is {1,2,3}, The next number is 5, Then the sequence is {1,2,3,5}, End . Now in the sequence 4 Elements , So the number of his longest subsequence is 4, But this sequence is a pseudo sequence , The elements inside , Not really the longest ascending subsequence , It is only the same as the number of the longest ascending subsequence . Because the binary search is used when searching , So the time complexity is o（nlogn）.
Implementation code ：
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int arr[500], n, dp[500], ans = -1;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
/* The core code for solving the number of the longest subsequence */
/* ********************************************** */
int k = 1;
dp[k] = arr[1];
for(int i = 2; i <= n; i++){
if(dp[k] < arr[i]) dp[++k] = arr[i]; // If it's bigger than the last element , Then add at the end
else *(lower_bound(dp + 1, dp + 1 + k, arr[i])) = arr[i]; // If it is smaller than the last element , Then replace the first larger number in the sequence ;
}
/* ********************************************** */
printf(" The number of longest subsequences is ： %d", k);
return 0;
}Tag path ：
O( ) Algorithm marking path , Just use an array of record precursors pre that will do .
Still use the sequence just now ：（7, 9, 6, 10, 7, 1, 3） Respectively （a1, a2, a3, a4, a5, a6, a7）
In the beginning a1 = 7, Make dp[ 1 ] = 1, pre[1] = 1; Then look at the next element a2 = 9, Make dp[ 2 ] = 1, pre[2] = 2, Then it needs to be checked i Whether there is one smaller than him in front because a1 < a2 and dp[ 1 ] + 1 > dp[ 2 ], therefore dp[ 2 ] = dp[ 1 ] + 1 == 2, Also update the tag pre[2] = 1; Then look at the next element a3 = 6, Make dp[ 3 ] = 1, pre[3] = 3, Then you need to check the previous elements a1 And a2 Is there anyone smaller than him , There is no such thing as , Spicy? up to now , The subsequence is himself . Then look at the next element a4 = 10; Make dp[ 4 ] = 1, pre[4] = 4; Then you need to check the previous elements in turn a1 And a2 And a3 Is there anyone smaller than him , Take a look a1 Smaller than it , And ,dp[ 1 ] + 1 > dp[ 4 ] So dp[ 4 ] = dp[ 1 ] + 1 == 2, pre[4] = 1, That at this time a1 And a4 Can form a length of 2 The ascending subsequence of , Let's see if we can form longer subsequences , So let's take a look again a2 , a2 < a4 And dp[ 2 ] + 1 == 3 > dp[ 4 ] == 2 So dp[ 4 ] = dp[ 2 ] + 1 == 3, pre[4] = 2, the a4 Undertake in a2 Later than in a1 Better after , Undertake in a2 The following sequence is ：a1 a2 a4 , Form a length of 3 The ascending subsequence of ; Then I'll see a3 , a3 < a4 But it's a pity d[ 3 ] + 1 == 2 < dp[ 4 ] == 3 , So you can't put a4 Add to a3 Behind . Then repeat the above process , Update all pre.
dp 1 2 1 3 2 1 2 pre 1 1 3 2 3 6 6
maximal dp The value is 3, So the longest subsequence length is 3, The last element is 4 Location . The trace path is ：4 -> pre[4] == 2 -> pre[2] == 1 -> pre[1] == 1( stop it ) Path is 4,2,1, This is flashback , Because I looked for it from the back .
Topic linking ：http://acm.hdu.edu.cn/showproblem.php?pid=1160 A classic LIS The topic of path marking .
The question ： give n A mouse . Each mouse has a corresponding weight and speed. Now it needs to come from here n In the sequence of mice , Find the longest sequence , Satisfy the mouse weight Strictly increasing ,speed Strictly decreasing , There may be weight and speed All the same mice .
Answer key ： Let's follow speed Descending sort , The rest just need to find weight Strictly increasing subsequences of , So it turns to the problem of finding the longest ascending subsequence .
#include<bits/stdc++.h>
#define up(i, x, y) for(ll i = x; i <= y; i++)
#define down(i, x, y) for(ll i = x; i >= y; i--)
#define bug printf("***************************\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define lk k<<1
#define rk k<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 7;
const double pi = acos(-1);
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;
int cnt, ans, loc, x, y;
int dp[maxn], pre[maxn], path[maxn];
struct node
{
int w, v, id;
}a[maxn];
bool cmp(node a, node b)
{
if(a.v != b.v)
return a.v > b.v;
return a.w < b.w;
}
int main(int argc, char const *argv[])
{
while(cin >> x >> y)
{
a[++cnt].w = x;
a[cnt].v = y;
a[cnt].id = cnt;
}
sort(a + 1, a + 1 + cnt, cmp);
for(int i = 1; i <= cnt; ++i)
{
dp[i] = 1;
pre[i] = i; // initialization , Take one element as a subsequence , Then your precursor node is yourself
for(int j = 1; j < i; ++j)
{
if(a[j].w < a[i].w && dp[i] < dp[j] + 1 && a[j].v != a[i].v)
//1. Satisfy w Monotonic strictly increasing 2. Can be updated 3. Because the speed is strictly monotonically decreasing , So add dp[j].v != d[i].v This condition
{
dp[i] = dp[j] + 1; // The current sequence is ai Undertake in aj after , therefore ai The precursor node of is j node
pre[i] = j; // Change the precursor node
}
if(ans < dp[i]) // Update the length of the longest subsequence of the record , And the position of the element at the end of the longest subsequence
{
ans = dp[i]; // Update the length of the longest subsequence of the record
loc = i; // Update the position of the element at the end of the longest subsequence , To facilitate the output path
}
}
}
for(int i = 1; i <= ans; i++)
{
path[i] = a[loc].id; // Need to record the original real location , So here it is path Fu is id, No loc
loc = pre[loc]; // Search according to the precursor array of records
}// The path here is from back to front , Pay attention to the reverse when outputting
printf("%d\n", ans);
for(int i = ans; i >= 1; i--)
{
printf("%d\n", path[i]);
}
return 0;
}nlogn Path marking of Algorithm ： The first thing to be clear is through nlogn The final sequence obtained by the algorithm is chaotic , Only the length of the sequence is valuable , So the last sequence is not a path . However, we can mark the actual position in the update process , Finally get the desired path . Just give an example . use mp The position of the array record in the sequence .
for instance （4, 2, 3, 1, 2,3,5） This sequence , Find his longest ascending subsequence , So look at , If the longest ascending sequence is found , Then according to greed , It should be most possible to make the elements of the sequence smaller as a whole , So that more elements can be added . Now open up a new array ,arr[ 10 ], { …….} –> This is his space , Now start to simulate the greedy algorithm to solve the longest ascending subsequence , The first number is 4, Add it first , So for { 4 }, And then mp[1] = 1, because a1 In the sequence is in the first position , therefore mp[1] = 1. Let's look at the next number 2, It is better than 4 Small , So if he and 4 Whether replacement can make the current subsequence （ He is a subsequence of this element ） To become smaller , It's more convenient to add elements in the future ？ Yes . So now for { 2 } And then mp[2] = 1, because a2 It is still in the first position in the sequence , therefore mp[2] = 1. Let's look at his next element 3, He is better than 2 Big , So, add it behind him ,{ 2, 3} And then mp[3] = 2, because a2 In the sequence, it is in the 2 A place , therefore mp[3] = 2. The next element is 1, It is better than 3 smaller , So, in order to ensure that the whole subsequence is as small as possible （ So that more elements can be added ）, Find the first number larger than him from the current sequence and replace it , Then it becomes { 1, 3} And then mp[4] = 1, because a4 In the sequence is in the first position , therefore mp[4] = 1, continue . The next number is 2, Then the sequence becomes { 1,2} And then mp[5] = 2, because a5 In the sequence, it is in the 2 A place , therefore mp[5] = 2, The next number is 3, Then the sequence is {1,2,3} And then mp[6] = 3, because a6 In the sequence, it is in the 3 A place , therefore mp[6] = 3, The next number is 5, Then the sequence is {1,2,3,5} And then mp[7] = 4, because a7 In the sequence, it is in the 4 A place , therefore mp[7] = 4, End . Now in the sequence 4 Elements , So the number of his longest subsequence is 4, But this sequence is a pseudo sequence , The elements inside , Not really the longest ascending subsequence , It is only the same as the number of the longest ascending subsequence . Because the binary search is used when searching , So the time complexity is o（nlogn）.
Sequence ： 4, 2, 3, 1, 2, 3, 5 mp: 1 1 2 1 2 3 4
// So look from the far right to the left ：
for(int i = n; i >= 1; i--)
{
if(mp[i] == top) // top Is the length of the longest subsequence
path[top--] = i; // path The path of the record
}
// Here the path is ： 4 5 6 7Topic linking ：http://acm.hdu.edu.cn/showproblem.php?pid=1160 Like the example above, it is just for practice nlogn The algorithm of .
#include<bits/stdc++.h>
#define up(i, x, y) for(ll i = x; i <= y; i++)
#define down(i, x, y) for(ll i = x; i >= y; i--)
#define bug printf("***************************\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define lk k<<1
#define rk k<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 7;
const double pi = acos(-1);
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;
int top, ans, len, x, y;
int st[maxn], mp[maxn], path[maxn];
struct node
{
int w, v, id;
}a[maxn];
bool cmp(node a, node b)
{
if(a.v != b.v)
return a.v > b.v;
return a.w < b.w;
}
int main(int argc, char const *argv[])
{
while(cin >> x >> y)
{
a[++len].w = x;
a[len].v = y;
a[len].id = len;
}
sort(a + 1, a + 1 + len, cmp);
top = 0;
st[++top] = a[1].w; // Push the first element onto the stack
mp[a[1].id] = 1; // Determine the position of the first element
for(int i = 2; i <= len; ++i)
{
if(a[i].w > st[top]) // If the current value is greater than the element at the top of the stack
{
st[++top] = a[i].w; // Join the stack
mp[a[i].id] = top; // Mark the actual position in the stack , It is convenient to find the path later
}
else
{
int l = 1, r = top; // Binary search for the first ratio a[i].w Big elements , To replace
while(l <= r)
{
int mid = (l + r) >> 1;
if(st[mid] < a[i].w)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
st[l] = a[i].w; // Replace
mp[a[i].id] = l; // Record the actual position in the stack
}
}
ans = top;
for(int i = len; i >= 1; i--)
{
if(mp[a[i].id] == top) // Find the path according to the location
path[top--] = a[i].id;
}
printf("%d\n", ans);
for(int i = 1; i <= ans; i++)
{
printf("%d\n", path[i]);
}
return 0;
}Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/130480.html Link to the original text ：https://javaforall.cn
边栏推荐
- 能升职加薪？PMP证书含金量浅析
- List announced | outstanding intellectual property service team in China in 2021
- Test cancellation 1
- EMC-电路保护器件-防浪涌及冲击电流用
- “丝路正青春 风采看福建”在闽外籍青年短视频大赛火热征集作品中
- PCB线路板塞孔工艺的那些事儿~
- Go - exe corresponding to related dependency
- 杰理之、产线装配环节【篇】
- Internet of things RFID, etc
- 九章云极DataCanvas公司蝉联中国机器学习平台市场TOP 3
猜你喜欢
随机推荐
杰理之烧录上层版物料需要【篇】
功利点没啥！
名单揭晓 | 2021年度中国杰出知识产权服务团队
“丝路正青春 风采看福建”在闽外籍青年短视频大赛火热征集作品中
pytest合集（2）— pytest运行方式
联想电脑怎么连接蓝牙耳机？
JS how to get a list of elements in a collection object
MySQL清空表数据
leetcode刷题：栈与队列07（滑动窗口最大值）
都能看懂的LIS（最长上升子序列）问题[通俗易懂]
选择在同花顺上炒股开户可以吗？安全吗？
cmake工程化相关
物联网rfid等
2022熔化焊接与热切割上岗证题目模拟考试平台操作
最近公共祖先离线做法（tarjan）
vscode的使用
leetcode刷题：栈与队列02（用队列实现栈）
按照功能对Boost库进行分类
leetcode刷题：二叉树03（二叉树的后序遍历）
PMP证书真的有用吗？