yet LIS

形式化题目

有 $n$ 个位置，每个位置 $i$ 有一个已按非降序排好的候选值集合 $a_{i,1} \leqslant a_{i,2} \leqslant \cdots \leqslant a_{i,k}$ 。从每个位置恰好选择一个值，构成序列 $x_1, x_2, \ldots, x_n$ 。求所有可能序列中，最长严格上升子序列（LIS）长度的最大值。

思路

一句话本质：把经典 LIS 贪心表的"逐数更新"改为"同位置候选先统一评估、再统一写回"，避免同一位置的候选值互相接龙。

直接暴力枚举会怎样？

枚举每个位置选哪个候选值，共 $k^n$ 种方案，每种跑一遍 LIS。先看这个朴素解：

cpp

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
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 19:06
 * update_at: 2026-08-28 19:06
 */
// brute.cpp：小数据暴力解，使用选择序列递归枚举所有可能。
// 每一层递归在为"第 dep 个位置"选择候选值下标（1..k），
// 生成完整的 choose[] 后，在叶子节点按选出的序列跑标准 O(n^2) LIS，
// 所有方案里取最大的 LIS 长度就是答案。
// 只能处理很小的数据（k^n 种方案），用于对拍验证 main.cpp。
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 10;
const int MAXN = 15;

int k, n;
int cand[MAXN][MAXK]; // cand[i][j] = 第 i 个位置的第 j 个候选值
int choose[MAXN];     // choose[i] = 第 i 个位置选的候选值下标（1..k）
int seq[MAXN];        // 由 choose 生成的完整序列
int ans;

// 对当前完整选择序列 seq[1..n] 跑标准 O(n^2) 的 LIS，返回长度。
int calc_answer() {
    int dp[MAXN] = {0};
    int best = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int t = 1; t < i; t++) {
            if (seq[t] < seq[i]) dp[i] = max(dp[i], dp[t] + 1);
        }
        best = max(best, dp[i]);
    }
    return best;
}

// dfs(dep) 为第 dep 个位置选择候选值下标，生成完整选择序列后在叶子统计。
void dfs(int dep) {
    if (dep == n + 1) {
        for (int i = 1; i <= n; i++) seq[i] = cand[i][choose[i]];
        ans = max(ans, calc_answer());
        return;
    }

    // 这一层在选择第 dep 个位置用哪个候选值（共 k 种选择）。
    for (int c = 1; c <= k; c++) {
        choose[dep] = c;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> k >> n;   // 注意输入顺序：k 在前，n 在后
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) cin >> cand[i][j];
    }

    dfs(1);
    cout << ans << '\n';
    return 0;
}

这个暴力把每一层递归看作"第 dep 个位置在 k 个候选值里选一个"的选择序列，生成完整选择后到叶子节点跑标准 $O(n^2)$ LIS 并更新答案。它枚举了所有可能，但 $k^n$ 是天文数字， $n=1000$ 时完全不可行。

每个位置只有一个数时，LIS 怎么求？

经典 LIS 贪心：维护 $v[L]$ = 长度为 $L$ 的严格上升子序列的最小结尾值， $v$ 在可达区间上严格递增， $v[L] = \infty$ 表示长度 $L$ 不可达。新数 $x$ 的最优新长度 = 最大的 $L$ 使 $v[L] < x$ ，然后 $v[L+1] = \min(v[L+1], x)$ 。

现在每个位置有 $k$ 个候选数，直接把 $k$ 个数当成"独立的数"依次处理会发生什么？

会非法接龙：候选 $[1, 100]$ 中， $1$ 先更新出"长度为 $2$ 、结尾 $100$ "的假链， $100$ 再基于它算出"长度 $3$ "——其实只用了同一个位置的两个数。一个位置只能用一次。

怎样阻止同位置接龙？

把一轮拆成两步：第一步用"上一阶段结束时的 $v$ 表"一次性算出每个候选值的最优长度 $dp[j]$ （期间表不被修改）；第二步把 $k$ 个更新统一写回。这就是滚动 $new\_dp$ 、避免同阶段踩踏。

为什么每个长度只保留一个最小结尾值就够？

$dp$ 值范围只有 $1..n$ ；对同一长度 $L$ ，结尾值越小，未来能接上的数越多，越优。所以表长只需 $O(n)$ ， $k$ 个候选值里"同长度取最小"由 $\min$ 更新自动完成。

对每个候选值都从表头找"最大可接长度"，能更快吗？

候选行已排序、单调不降， $v$ 表严格递增，所以"最大可接长度"随 $j$ 单调不降——用双指针 $p$ 从上一轮的位置继续推进：while (p+1 <= n && v[p+1] < a[j]) p++;，则 $dp[j] = p+1$ 。一轮内 $p$ 总共只前进 $O(n)$ 次，每轮评估 $O(k+n)$ 。

样例推演（DP 表）

这张表展示样例 $k=2, n=2$ （候选 $[1\ 3]$ / $[1\ 2]$ ）中 $v$ 表随每个候选值的演化：

阶段	候选值 $a_j$	评估用的旧 $v$ 表	$dp[j]$	写回后的 $v$ 表
初始	—	—	—	$v=[\infty, \infty]$
位置 1	1	$[\infty, \infty]$ ，无可接	1	$v[1]=1$
位置 1	3	$[\infty, \infty]$ （旧表，非更新后）	1	$v[1]=\min(1,3)=1$
位置 2	1	$[1, \infty]$ ， $v[1]<1$ 不成立	1	$v[1]=\min(1,1)=1$
位置 2	2	$[1, \infty]$ ， $v[1]=1<2$	2	$v[2]=2$

观察点：候选值 $3$ 的 $dp$ 用的是旧表 $[\infty,\infty]$ ，因此不会与候选值 $1$ 接龙出伪链；最后 $v[2] \neq \infty$ ，说明存在长度为 $2$ 的链（选 $1$ 、 $2$ ），答案为 $2$ 。

正确性归纳：处理完前 $i$ 个位置后， $v[L]$ 恰为所有合法选择中长度为 $L$ 的链的最小结尾值——转移对每个候选值枚举了所有可接长度（完备），最小结尾永不劣（充分），两步写回保证同一位置不接龙。

代码

cpp

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
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 19:06
 * update_at: 2026-08-28 19:06
 */
/**
 * C. yet LIS
 * 每个位置 i 有 k 个已排序的候选值 a[i][1] <= ... <= a[i][k]，
 * 每个位置恰好选一个数构成序列，求所有可能序列的最长严格上升子序列的最大长度。
 *
 * 做法（官方双指针，O(n^2 + n*k)）：
 *   v[L] = 处理完已走过的位置后，长度为 L 的严格上升子序列的最小结尾值。
 *   v[1..] 严格递增，v[L] = INF 表示长度 L 目前不可达。
 *   对当前位置的 k 个候选值（已排序）：
 *     1) 先用"上一阶段"的 v 一次性算出每个候选值的 dp[j]：
 *        双指针 p 表示最大的下标满足 v[p] < a[j]，则 dp[j] = p + 1。
 *     2) 再统一更新 v[dp[j]] = min(v[dp[j]], a[j])。
 *    分两步是为了避免同一位置的候选值互相"接龙"（同一个位置用了两个数）。
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 5005;   // k 的最大值
const int MAXN = 1005;   // n <= 1000，留几个空位
const int INF = 1000000010; // 比所有值(<=1000)都大，表示"不可达"

int k, n;          // 每个位置 k 个候选值，共 n 个位置
int a[MAXK];       // 当前这一行的 k 个候选值（题目保证已排序）
int v[MAXN];       // v[L] = 长度为 L 的严格上升子序列的最小结尾值，INF 表示不可达
int dp[MAXK];      // dp[j] = 本轮选择候选值 a[j] 能得到的最长上升子序列长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> k >> n;   // 注意输入顺序：k 在前，n 在后
    for (int L = 1; L <= n; L++) v[L] = INF;

    for (int i = 1; i <= n; i++) {          // 依次处理每个位置
        for (int j = 1; j <= k; j++) cin >> a[j];

        // 第一步：用上一阶段结束时的 v，一次性算出所有 dp[j]。
        // v 严格递增、a[j] 单调不降，所以 p 单调不降，可以双指针。
        int p = 0;                          // 最大的下标满足 v[p] < a[j]
        for (int j = 1; j <= k; j++) {
            while (p + 1 <= n && v[p + 1] < a[j]) p++;
            dp[j] = p + 1;                  // 长度 dp[j]-1 的链都能接上 a[j]
        }

        // 第二步：统一应用更新。同一长度取更小的结尾值（min 自动完成）。
        for (int j = 1; j <= k; j++) {
            v[dp[j]] = min(v[dp[j]], a[j]);
        }
    }

    // 答案 = 最大的可达长度
    for (int L = n; L >= 1; L--) {
        if (v[L] != INF) {
            cout << L << '\n';
            return 0;
        }
    }
    return 0;
}

复杂度

每轮双指针 $O(k+n)$ ，共 $n$ 轮，总 $O(n^2 + nk)$ ；空间 $O(n + k)$ 。

总结

这题是经典 LIS 贪心的直接扩展，卡点不在"找 LIS"，而在"同一位置有多个互斥候选值"：必须把"评估"和"写回"分两步，否则候选值会自我接龙。理解 $v[L]$ 的"最小结尾支配"性质后，双指针只是把已排序输入带来的单调性变现。类似"每阶段多选一求最长链"的问题都可以套这套先算后写 + 单调指针的模板。

目录

形式化题目

思路

样例推演（DP 表）

代码

复杂度

总结