必须经过指定点的最大和非递减子序列（带 checkpoint 的 LIS 变种）

作者提米哥

你写过最长递增子序列（LIS）？那只是热身。
今天这个题，表面像 LIS，实则“披着羊皮的狼”——它强制你必须经过几个指定下标（叫 checkpoint），还要让整个子序列非递减，并且总和最大。

不是求长度，不是求个数，是求「钱」：每个数当金币，怎么捡才能最赚？但路上有路标——你必须踩中每一个路标，少一个都不行。

✅ 有效子序列 = 从头开始 → 经过 checkpoint[0] → checkpoint[1] → … → checkpoint[p−1] → 到结尾
❌ 无效 = 路标顺序错、踩了路标但后面变小、漏踩任意一个路标

🔍 第一步：先看路标本身合不合理

如果 checkpoint 是 [2, 4]，对应数组 a = [10, 20, 15, 30, 40]（注意：下标从 1 开始）：
→ a[2] = 20，a[4] = 30 → 20 ≤ 30 ✔️ 合理，能走通
但如果 a = [50, 40, 30, 20]，checkpoint 还是 [1, 4]：
→ a[1] = 50，a[4] = 20 → 50 > 20 ❌ 直接失败，输出 -1

所以代码第一件事： 

// 检查所有 checkpoint 对应的值是否本身非递减
for (int i = 1; i < p; i++) {
    if (a[cp[i]] < a[cp[i-1]]) {  // 注意：是 <，不是 <=，因为题目要求“非递减”，允许相等
        cout << -1 << endl;
        return 0;
    }
}

🧩 第二步：把大问题切成小段，逐段 DP

既然必须按顺序经过 cp[0], cp[1], ..., cp[p−1]，那就把整条路切开：

[1 ... cp[0]] → [cp[0]+1 ... cp[1]] → ... → [cp[p−2]+1 ... cp[p−1]] → [cp[p−1]+1 ... n]

每一段只负责一件事：
✅ 从该段起点出发，以 checkpoint 结尾（或结尾后继续延伸），且全程非递减
✅ 累加每段的「最大可能和」

核心 DP 状态：
dp[i] = 以位置 i 结尾的、满足非递减约束的最大子序列和

转移逻辑很简单：
– 想把 a[i] 加进来？得保证前面有个 j < i，且 a[j] ≤ a[i]，而且 dp[j] 已算出
– 那就试所有 j，挑 dp[j] + a[i] 最大的那个

💻 完整可运行代码（已加中文注释）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;

    vector<int> a(n + 1);  // 数组下标从 1 开始，更贴合题目描述
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> cp(p);
    for (int i = 0; i < p; i++) cin >> cp[i];  // 输入 checkpoint 下标（也是从 1 开始）

    // ✅ 第一关：检查 checkpoint 值是否天然递减（无法修复）
    for (int i = 1; i < p; i++) {
        if (a[cp[i]] < a[cp[i-1]]) {
            cout << -1 << endl;
            return 0;
        }
    }

    int prev_idx = 1;      // 当前处理段的左边界（初始为 1）
    int prev_val = 0;      // 上一个 checkpoint 的值（初始为 0，确保第一个数可选）
    int total = 0;         // 总最大和

    // 🔁 处理每个 checkpoint 段：从 prev_idx 到 cp[k]
    for (int k = 0; k < p; k++) {
        int L = prev_idx;
        int R = cp[k];

        // dp[i] 表示：在 [L, R] 段内，以位置 i 结尾的最大非递减子序列和
        vector<int> dp(n + 1, 0);

        for (int i = L; i <= R; i++) {
            // 如果当前值比上一个 checkpoint 值还小，不能选（破坏非递减性）
            if (a[i] < prev_val) continue;

            dp[i] = a[i];  // 至少可以单独选自己

            // 尝试接在前面某个 j 后面：要求 a[j] <= a[i]，且 dp[j] 已计算（>0 表示合法）
            for (int j = L; j < i; j++) {
                if (a[j] <= a[i] && dp[j] > 0) {
                    dp[i] = max(dp[i], dp[j] + a[i]);
                }
            }
        }

        // 如果到 checkpoint 位置 R 都没算出合法值，说明这段走不通
        if (dp[R] == 0) {
            cout << -1 << endl;
            return 0;
        }

        total += dp[R];        // 加上这段以 R 结尾的最大和
        prev_val = a[R];       // 更新“上一个值”，用于下一段约束
        prev_idx = R + 1;      // 下一段从 R+1 开始
    }

    // ➕ 最后一段：从最后一个 checkpoint 后面到数组末尾
    vector<int> dp(n + 1, 0);
    for (int i = prev_idx; i <= n; i++) {
        if (a[i] < prev_val) continue;  // 仍要满足非递减延续

        dp[i] = a[i];
        for (int j = prev_idx; j < i; j++) {
            if (a[j] <= a[i] && dp[j] > 0) {
                dp[i] = max(dp[i], dp[j] + a[i]);
            }
        }
    }

    // 这段不强制结尾，取所有可能结尾中的最大值
    int best_tail = 0;
    for (int i = prev_idx; i <= n; i++) {
        best_tail = max(best_tail, dp[i]);
    }
    total += best_tail;

    cout << total << endl;
    return 0;
}

🧠 为什么这样设计？三句话讲透

  • 分段不是偷懒，是破局关键：全局 DP 状态爆炸；分段后每段只关心“从哪来、到哪去、值够不够大”，状态清晰可控。
  • fail-fast 很重要：先验检查 checkpoint 值顺序，10 行代码省掉全部无效计算。
  • max sum ≠ max length：LIS 默认优化长度，这里每个数字是“金币”，我们要攒最多的钱，所以 dp[i] 存的是和，不是长度。

🚀 实战小贴士（面试/刷题用）

  • 遇到“必须包含某些点”的优化题，第一反应：按这些点切片 + 分段 DP
  • 边界检查永远放最前：checkpoint 值是否递减？索引是否越界？
  • 所有 DP 题，先问自己：状态定义是什么？转移依赖什么条件？答案怎么合并？

直达网址：https://dev.to/tommyzeng/the-problem-that-looks-like-lis-but-isnt-3n6g

作加

微信联系：timidamen

类似文章