由于你帮助 Alice 回答得非常好,Sept 又找到了 Bob,希望能难倒他。 他给了要求 Bob 组成一个长度为 $n$ 的新的数列 $a$,其中数列 $a$ 的每一个元素 $a_i$ 都有 $k$ 个取值。 求所有可能的数列 $a$ 中的最长上升子序列的的最大长度。 由于 Sept 怕题目钛难,所以他答应 Bob,对于每个 $i$,$k$ 个取值不降。

输入格式

第一行两个数 $n$,$k$,意义如题述。 接下来 $n$ 行,每行 $k$ 个数,即 $a_i$ 的 $k$ 个取值。

输出格式

仅一行一个整数,即所有可能的数列 $a$ 中的最长上升子序列的最大长度。

输入样例:

2 2
1 3
1 2

输出样例:

2

说明

数列 $a$可能为 $[1,2]$,这时最长上升子序列的长度为2,是最长的长度。

数据范围:

对于10

题目分析

朴素的最长上升子序列问题:

题目分析

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

我们显然可以使用 DP:

设 f(i) 为 a[1 ~ i] 这个数列的最长上升子序列的长度。

那么: $$ \forall i \in {1, 2, \ldots, n}, \begin{cases} f(i) = 1 \quad \ f(i) = \max_{1\leq j< i}{f(j)} \text{if } \forall j \in {1, 2, \ldots, i-1}, \text{ we have } num[i] > num[j] \end{cases} $$

代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;

int n, a[N], dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for(int j = 1; j < i; ++j) if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
    }
    cout << *max_element(dp + 1, dp + n + 1);
    return 0;
}

而对于这道题, 数列 a 的每一个元素 ai 都有 k 个取值, 我们也可以将它考虑成二维的DP, 并且根据题目条件对于每个 i,k 个取值不降, 我们可以使用二分查找来优化时间。但是朴素的二维DP的时空复杂度仍然很大。

那么, 我们考虑贪心:

当遇到一个新的元素时,

  • 如果这个元素大于当前最长上升子序列的最后一个元素,那么将这个元素加入到最长上升子序列中;
  • 否则,将它尽可能地插入到现有的最长上升子序列中的相应位置”。

贪心的证明:

贪心选择性质: 先前的选择不会影响后续的选择。

在我们的贪心策略中, 插入一个新元素时的决策仅与当前元素有关,已选定的部分以及未考察的部分都不会影响选择。

最优子结构: 整体的最优解可以由子问题的最优解推出。

我们在这个问题中需要找的是最长上升子序列,如果我们已经有了 a[1 ~ i- 1] 的最优解,那么当我们在处理第 i 个元素时,无论我们是选择将a[i]插入到现有的子序列中的某个位置,还是将其加入到LNS的最后面,a[1 ~ i] 的最优解必然可以由此推出。

所以,这个贪心策略是正确的。

那么,我们怎么实现这个算法呢?

精髓是创建一个数组 tailtail[i]用于存储所有长度为 i 的上升子序列里,结尾元素最小的那一个上升子序列的结尾元素的值。

由于每组 k个数据中只能选择一个, 如果我们从小到大遍历 a 将元素插入的话,我们不一定只选择了一个。而我们如果从大到小遍历插入的话,一定只选择了一个。(这里和完全背包,01背包问题的思路有一点相似,概篇幅所限,不再详细解释)

注:查询 tail 中的元素时, 由于 tail 本身的性质, 元素的值一定是单调递增的,可以使用二分查找优化时间(这里为了代码简洁直观,不再手动编写求 tail 中第一个大于等于 a[j] 的元素的下标的二分查找函数,有需要的同学可以查看 KeChang's Blog, 内收录有二分查找例题)。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 10, M = 5e3 + 10;

int n, k, tail[N], a[M];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> k >> n;
    memset(tail, 0x3f, sizeof tail);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) cin >> a[j];
        for (int j = k; j >= 1; --j) {
            int pos = lower_bound(tail + 1, tail + i + 1, a[j]) - tail;
            tail[pos] = a[j];
            ans = max(ans, pos);
        }
    }
    cout << ans;
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status