跳转至

最长上升子序列模型 1

LIS: Longest In 2. "倒数第二个数"到底是谁 -> 由谁转移而来 3. easing Sequence

895 最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少

输入样例：

Text Only
1
2
7
3 1 2 1 8 5 6

输出样例：

Text Only
1
4 (1 2 5 6)

动态规划分析:

  1. 状态表示: f[i]
    1. 集合: 所有以 a[i] 结尾的 严格单调上升 子 2. "倒数第二个数"到底是谁 -> 由谁转移而来
    3. 属性: max / min / 数量
  2. 状态计算: 集合划分
    1. 划分依据: "最后一个不同的点"
    2. “倒数第二个数”到底是谁 -> 由谁转移而来

代码:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

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

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; // 只有a[i]一个数
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i]) // 确保合法
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    printf("%d\n", res);

    return 0;
}

1017 怪盗基德的滑翔翼

任选一个楼房 + 选定一个方向 + 只能向“下”跳:

最多可以经历多少个房?

分析:

如果确定了方向和起点, 最长的距离是什么？

  • 左跳
  • 起点: a[i]
  • max距离: 以 a[i] 结尾的 最长上升子序列
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int h[N];
int f[N];

int main()
{
    int T;
    scanf("%d", &T); // T 组测试数据
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]); // 输入楼房

        int res = 0;
        // 正向求解 LIS 问题
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (h[i] < h[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }

        memset(f, 0, sizeof f);
        // 反向求解 LIS 问题
        for (int i = n - 1; i >= 0; i -- )
        {
            f[i] = 1;
            for (int j = n - 1; j > i; j -- )
                if (h[i] < h[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }

        printf("%d\n", res);
    }

    return 0;
}

1014 登山

  • 条件1: 编号递增 顺序浏览 -> 必须是子序列
  • 条件2: 相邻两个景点不能相同 -> 严格单调
  • 条件3: 一旦开始下降, 就不能再上升 -> 严格单调上升 + 严格单调下降

目标: 最多能浏览多少景点

  • f[i]: 从左向右到 a[i]
  • g[i]: 从右向左到 a[i]
  • 答案: f[i] + g[i] -1
  • 注意: 先预处理一遍f和g，减少复杂度
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    // 输入数据
    for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);

    // 预处理一遍: 正向最长单调上升子序列
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (h[i] > h[j])
                f[i] = max(f[i], f[j] + 1);
    }

    // 预处理一遍: 反向最长单调上升子序列
    for (int i = n - 1; i >= 0; i -- )
    {
        g[i] = 1;
        for (int j = n - 1; j > i; j -- )
            if (h[i] > h[j])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, f[i] + g[i] - 1);

    printf("%d\n", res);

    return 0;
}

482 合唱队形

跟 1014 完全对偶

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (h[j] < h[i])
                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 (h[j] < h[i])
                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);

    // 跟 1014登山 完全对偶
    printf("%d\n", n - res);

    return 0;
}

1012 友好城市

条件:

  1. 每个城市只能建立一个桥
  2. 所有桥之间不能相交
  3. 建桥模式合法

思路: 一边排序，另一边“最长上升子序列”

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 基于 “pair” 默认排序

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
        scanf("%d%d", &city[i].first, &city[i].second);
    sort(city, city + n); // pair默认按照 "第一关键字" 排序

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (city[i].second > city[j].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    printf("%d\n", res);

    return 0;
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 基于 struct 手动指定排序 (recommended)

#include<bits/stdc++.h>

using namespace std;

const int N = 5010;

struct city_pair{
    int city1;
    int city2;
};
city_pair cities[N];

int n;
int f[N]; // 动态规划

bool cmp (city_pair a, city_pair b)
{
    return a.city1 < b.city1;
}

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> cities[i].city1;
        cin >> cities[i].city2;
    }

    sort(cities+1, cities+n+1, cmp);
    // sort (起始地址, 结束地址, 比较函数)
    // sort(a,b): [a, b). 左闭右开
    // cmp: 回调函数. 可以自定义排序方式

    for (int i=1; i<=n; i++)
    {
        f[i] = 1;

        for (int j=1; j<i; j++)
        {
            if (cities[j].city2 < cities[i].city2)
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i=1; i<=n; i++)
    {
        ans = max(ans, f[i]);
    }
    cout << ans << endl;

    return 0;
}

1016 最长上升子序列和

动态规划分析:

  1. 状态表示: f[i]
    1. 集合: 所有以 a[i] 结尾的 上升 子序列
    2. 属性: 和的 max / min / 数量
  2. 状态计算: 集合划分
    1. 划分依据: "最后一个不同的点"
    2. “倒数第二个数”到底是谁 -> 由谁转移而来

代码:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int w[N];
int f[N];

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = w[i];
        for (int j = 0; j < i; j ++ )
            if (w[i] > w[j])
                f[i] = max(f[i], f[j] + w[i]);
        res = max(res, f[i]);
    }

    printf("%d\n", res);

    return 0;
}