优化#

定义数组 d：

• d[len] 表示：长度为 len 的所有递增子序列中，末尾元素的最小值．
• 若不存在长度为 len 的递增子序列，则记为 INF（$\infty$）．

不难发现，d 数组是严格单调递增的（对于严格递增子序列）：

为什么？因为长度为 len+1 的子序列末尾，一定大于某个长度为 len 的子序列末尾，而 d[len] 取最小值，所以必然有 d[len] < d[len+1]．

遍历原序列中的每一个元素 x = A[i]：

1. 在 d 数组中，找到最大的下标 j，使得 d[j] < x．
2. 令目标位置为 pos = j + 1．
3. 更新 d[pos] = x．

注意：

• 找到一个长度为 j 的尾巴比 x 小的子序列，把 x 接在后面，会得到 长度为 j+1 的子序列．所以必须更新 d[j+1]，而不是 d[j]．
• 不需要更新 $d[pos-x],x\in \mathbb{N*}$，是因为当前的值比 d[pos-x] 大．

由于 d 严格递增，“最大的 j 使 d[j] < x” 等价于 “找到第一个 pos 使 d[pos] >= x”．

此时有对应关系：

因此，算法可以简化为：在 d 数组中二分查找第一个大于等于 x 的位置 pos，然后将 d[pos] 替换为 x．

复杂度分析

• 每次查找使用二分查找：$O(logn)$
• 总共遍历 n 个元素
• 总时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$

标程

使用 lower_bound 直接查找第一个 >= x 的位置

1
#include <bits/stdc++.h>
2
using namespace std;
3
int ans;
4

5
const int N = 5e5 + 100;
6
int n, a[N], dp[N]; // dp[i] = 长度i时，末尾最小值
7

8
int main() {
9
    cin >> n;
10
    memset(dp, 0x3f, sizeof(dp));
11
    for (int i = 1; i <= n; i++) {
12
        cin >> a[i];
13
    }
14
    for (int i = 1; i <= n; i++) {
15
        int pos = lower_bound(dp + 1, dp + n + 1, a[i]) - dp;
16
        dp[pos] = a[i];
17
        ans = max(ans, pos);
18
    }
19
    cout << ans;
20
    return 0;
21
}

如果需要求出子序列具体的元素，需要额外维护：

• idx[i] 表示 dp[i] 所取元素的下标，即满足 dp[i] = a[idx[i]]
• pre[i] 表示 a[i] 在目标序列的前驱

在找到 pos 之后，

• 若 pos 为 1，则表示 a[i] 为开头，设置 pre[i] = 0
• 否则，a[i] 会接在 dp[pos-1] 之后，设置 pre[i] = idx[pos-1]

最后，从最后一个元素开始，也就是 dp[ans]，往前跳，将每一次跳的结果保留在 answer 中，并翻转，就是路径．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
int ans;
4

5
const int N = 5e5 + 100;
6
int n, a[N], dp[N]; // dp[i] = 长度i时，末尾最小值
7
int idx[N], pre[N];
8
// idx[i] := dp[i]值对应元素的下标
9
// pre[i] := a[i]可以接在a[pre[i]]的后面
10

11
int main() {
12
    cin >> n;
13
    memset(dp, 0x3f, sizeof(dp));
14
    for (int i = 1; i <= n; i++) {
15
        cin >> a[i];
16
    }
17
    for (int i = 1; i <= n; i++) {
18
        int pos = lower_bound(dp + 1, dp + n + 1, a[i]) - dp;
19
        if (pos == 1) {
20
            // 如果 a[i] 可以作为开头
21
            pre[i] = 0; // a[i] 前面没有东西
22
        } else {
23
            // 否则 a[i] 会接在 dp[pos-1] 后面
24
            pre[i] = idx[pos - 1];
25
        }
26
        // 维护数据
27
        idx[pos] = i;
28
        dp[pos] = a[i];
29
        ans = max(ans, pos);
30
    }
31
    vector<int> answer;
32
    int ptr = idx[ans];
33
    while (ptr != 0) {
34
        answer.push_back(a[ptr]);
35
        ptr = pre[ptr];
36
    }
37
    reverse(answer.begin(), answer.end());
38
    for (auto k : answer) {
39
        cout << k << " ";
40
    }
41
    return 0;
42
}

01 背包#

有 $n$ 个物品和一个容量为 $w$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量．

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为0-1 背包问题．

定义 dp[i][j] 表示考虑前 i 个元素，背包占用空间达到 j，所能够获取的最大空间．初始时 dp[1][0]=0

对于所有的物品，都有选和不选两种选择，因此，有如下的状态转移方程：

不难发现，dp[i][j] 依赖于以下项：

• dp[i-1][j]
• dp[i-1][j-w[i]]

由于第一维只与 i-1 有关，因此，可以倒着遍历 j，如果这样，第一维状态就可以省去．

完全背包#

有 $n$ 种物品和一个容量为 $w$ 的背包，每种物品有重量 $w_i$ 和价值 $v_i$ 两种属性，且每一种都有无限个，要求选若干物品放入背包使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量．

相对于 01 背包，完全背包的每个物品可以取无限个，状态定义和 01 背包一样，不过，对于每一个物品，都有选 0 个、选 1 个……直到重量到达 $w$．因此，有如下转移方程：

显然，这样时间复杂度是 $O(n^3)$．

优化

在 dp[i][j] 的转移中，需要枚举 dp[i-1][j-1*w[i]]、dp[i-1][j-2*w[i]]、dp[i-1][j-3*w[i]]……而在 dp[i][j-w[i]] 的转移中，需要枚举 dp[i-1][j-2*w[i]]、dp[i-1][j-3*w[i]]……显然，我们发现，dp[i][j] 的枚举之比 dp[i][j-w[i]] 多了一个 dp[i][j-w[i]]．

由此，就有以下转移方程：

由于第一维只与 i-1 和 i 有关，因此，可以正着遍历 j，如果这样，第一维状态就可以省去．

多重背包#

有 $n$ 种物品和一个容量为 $w$ 的背包，每种物品有重量 $w_i$ 和价值 $v_i$ 两种属性，且每一种都有 $s[i]$ 个，要求选若干物品放入背包使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量．

相对于 01 背包，多重背包可以选择至多 $s[i]$ 次，对于每一个物品，都有选 0 个、选 1 个……选 $s[i]$ 个．因此，有如下转移方程：

显然，转移是 $O(n^3)$．

优化 1

对于 $j - s[i] \times w[i] < 0$ 的情况，说明 $s[i]$ 个都取不到，此时退化成完全背包，可以使用完全背包的关系式．

优化 2

对于一件有 $s[i]$ 个的物品，我们可以将其二进制拆解为：

，其中 $k$ 是满足 $n - 2^k + 1 > 0$ 的最大整数．

设其二进制拆解的第 $i$ 项为 $d_i$，就可以将 $s[i]$ 件物品拆解为 $d_1$ 件价值为 $d_1\times v[i]$ 、$d_2$ 件价值为 $d_2\times v[i]$ ……的物品．这样转化为 01 背包．