AcWing 1017. Kidd's glider

sample input ：

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

sample output ：

6
6
9

When confirmed Direction and The starting point After finishing , What is the longest distance ？

The starting point ：a[i]

The longest ： With  a[i]  Starting from Longest ascending subsequence （LIS）

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

const int N = 110;

int n;
int a[N], f[N];

int main()
{
    int T;
    cin >> T;
    while(T -- )
    {
        cin >> n;
        for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        
        //  Forward solution  LIS
        int res = 0;
        for(int i = 1; i <= n; i ++ )
        {
            f[i] = 1;
            for(int j = 1; j < i; j ++ )
                if(a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        
        //  Reverse solution  LIS
        for(int i = n; i; i -- )
        {
            f[i] = 1;
            for(int j = n; j > i; j -- )
                if(a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        
        cout << res << endl;
    }
    return 0;
}

AcWing 1014. Mountaineering  

sample input ：

---

sample output ：

4

The title includes the following Conditions ：

1. according to Number increment In order to browse （ Subsequence ）
2. Two adjacent scenic spots cannot be the same height （ Strictly monotonous ）
3. Once you start to fall, you can't rise  

The goal is ： Ask how many scenic spots you can visit at most

Two LIS Then the maximum value of addition is solved

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

const int N = 1010;

int n;
int a[N];
int f[N], g[N];


int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for(int j = 1; j < i; j ++ )
            if(a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    
    for(int i = n; i; i -- )
    {
        g[i] = 1;
        for(int j = n; j > i; j -- )
            if(a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }
    
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
    
    cout << res << endl;
    
    return 0;
}

AcWing 1012. Friendly city

sample input ：

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

sample output ：

4

  all Legal way of building bridges All correspond to a Ascending subsequence of dependent variable

  therefore , The scenario , In the case of upper coordinate sorting , The order of the lower coordinates is not from small to large , It must be illegal （ There will be intersection ）

therefore , This question becomes ： The coordinates above the bridge are sorted from small to large , Find the length of the longest ascending subsequence of the lower coordinate

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;

typedef pair<int, int> PII;

int n;
PII q[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ ) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);
    
    int res = 0;
    for(int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++ )
            if(q[i].second > q[j].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    return 0;
}

AcWing 1016. The maximal ascending subsequence and  

sample input ：

7
1 7 3 5 9 4 8

sample output ：

18

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

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i ++ )
    {
        f[i] = a[i];
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + a[i]);
    }
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}

AcWing 1010. Interceptor missile  

sample input ：

389 207 155 300 299 170 158 65

sample output ：

6
2

This question is First question It's a classic LIS problem

For the second question , We use Greedy thought

Greedy process ：

Scan each number from front to back , For each number ：

        situation 1： If the end of the existing subsequence is less than the current number , Then create a new subsequence

        situation 2： Put the current number after the smallest subsequence greater than or equal to it

Greedy proof ：

1. How to prove that two numbers are equal ？ 

 A Represents the number of sequences obtained by greedy algorithm ,B Represents the optimal solution

 ① , From the properties of the optimal solution

 ②   Adjustment method

         Suppose that the scheme corresponding to the optimal solution is different from the current scheme

        Find the first different number .

        The optimal solution can be adjusted to the greedy solution through a finite number of exchanges , Without increasing the number of sequences

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

const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main()
{
    while(cin >> q[n]) n ++ ;
    
    int res = 0;
    for(int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++ )
            if(q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    
    cout << res << endl;
    
    int cnt = 0;
    for(int i = 0; i < n; i ++ )
    {
        int k = 0;
        while(k < cnt && g[k] < q[i]) k ++ ;
        g[k] = q[i];
        if(k >= cnt) cnt ++ ;
    }
    
    cout << cnt << endl;
    
    return 0;
}

 AcWing 272. The longest common ascending subsequence

4
2 2 1 3
2 1 2 3

sample output ：

2

The subject is Longest ascending subsequence and Longest common subsequence Combined version of , In terms of state representation and state calculation, it is a method that integrates these two topics .

State means ：

  On behalf of all a[1 ~ i] and b[i ~ j] China and Israel b[j] Public ascending subsequence at the end Set

The value of is equal to the length of the subsequence of the set Maximum  

State calculation ：

First of all, according to the Whether the public subsequence contains a[i], take f[i][j] The set represented is divided into two subsets that are neither heavy nor leaky

• It doesn't contain a[i] Subset , The maximum is f[i - 1][j]
• contain a[i] Subset , Continue to divide this subset , Based on The penultimate element of the subsequence is b[] Which number is in
  • The subsequence contains only b[j] a number , The length is 1
  • The penultimate number of subsequences is b[1] Set , The maximum length is f[i-1][1] + 1
  • ....
  • The penultimate number of subsequences is b[j - 1] Set , The maximum length is f[i-1][j-1] + 1

Get the following   How to do it

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
                for(int k = 1; k < j; k ++ )
                    if(b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i][k] + 1);
            }
        }
        
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    
    cout << res << endl;
    
    return 0;
}

And then we find that every time we cycle, we get maxv Is to meet a[i] > b[k] Of f[i - 1][k] + 1 The maximum prefix of .
So you can directly take maxv Mention the first layer of circulation outside , Reduce double counting , There are only two cycles left .

Take the maximum value at the end of the subsequence of the final answer enumeration .

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);

    for (int i = 1; i <= n; i ++ )
    {
        int maxv = 1;
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    printf("%d\n", res);

    return 0;
}