模拟

模拟就是让程序按照题目规定的顺序，把一个过程一步一步执行出来。它通常没有难记的公式，真正考查的是：能否把较长的文字规则翻译成明确的状态、操作顺序和边界判断。

示例：网格中的机器人

给定一张 n 行 m 列的网格、一台机器人的起点 (x, y) 和一串移动指令 s，求机器人执行完所有指令后的坐标。坐标的第一个数是行号，第二个数是列号。左上角为 (1, 1)，行号向下增大，列号向右增大。

机器人从左到右读取 s，每个字符尝试移动一格。U 向上，行号减 1。D 向下，行号加 1。L 向左，列号减 1。R 向右，列号加 1。只有目标格在第 1 到 n 行、第 1 到 m 列之内才移动。越界时留在原格，继续读下一条指令。

样例

3 4 2 2
UURRDDDRU

2 4

先在纸上走一遍

第 2、7、8 条指令尝试走出网格，执行这三条指令时位置保持原样。最后一条 U 从 (3, 4) 移到 (2, 4)，因此输出 2 4。

把单步规则翻译成代码

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

int main() {
    int n, m, x, y;
    string s;
    cin >> n >> m >> x >> y >> s;

    // 先试走一步，确认没有越界后再更新位置
    for (char c : s) {
        int nx = x, ny = y;

        if (c == 'U') nx--;
        else if (c == 'D') nx++;
        else if (c == 'L') ny--;
        else if (c == 'R') ny++;

        bool ok = nx >= 1 && nx <= n
                   && ny >= 1 && ny <= m;
        if (ok) {
            x = nx;
            y = ny;
        }
    }
    cout << x << ' ' << y << '\n';
}

复杂模拟先做“统一表示”

模拟题最常见的四类错误

贪心

贪心算法会按照某条规则不断做出当前选择，并且不回头修改。代码往往只有“排序 + 遍历”，但真正的难点是找到正确规则，并说明这个局部选择为什么一定能组成全局最优答案。

经典例子：选择最多不重叠区间

学校只有一间教室，有 n 个活动申请使用。第 i 个活动的开始和结束时间分别是 lᵢ、rᵢ。选中一个活动，就必须按原定时间完整举行。请从这些活动中选出尽可能多的活动，使教室在任意时刻最多被一个活动占用。

活动占用半开区间 [lᵢ, rᵢ)，即从开始时刻占用教室，在结束时刻腾出教室。按实际举行顺序看，只要后一个活动的开始时间大于或等于前一个活动的结束时间，两者就能连续安排。例如 [2, 3) 和 [3, 5) 可以都选，[2, 3) 和 [1, 4) 会冲突。

样例

6
1 4
6 8
2 3
4 7
5 6
3 5

4

先选哪个活动？

手算选择过程

把样例中的 6 个活动按结束时间从小到大排序。每次只比较当前活动的开始时间与上一个已选活动的结束时间。跳过冲突的活动时，已选活动的结束时间保持原样。

完整代码

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

struct Activity {
    long long l, r;
};

bool cmp(const Activity &a, const Activity &b) {
    if (a.r != b.r) return a.r < b.r;
    return a.l < b.l;
}

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

    int n;
    cin >> n;
    vector<Activity> a(n);
    for (Activity &e : a) {
        cin >> e.l >> e.r;
    }

    // 优先选择结束最早的区间，给后面留出更多空间
    sort(a.begin(), a.end(), cmp);

    int ans = 0;
    long long ed = LLONG_MIN;
    for (const Activity &e : a) {
        // 开始时间不早于上一个已选活动的结束时间
        if (e.l >= ed) {
            ans++;
            ed = e.r;
        }
    }
    cout << ans << '\n';
}

为什么“最早结束”一定正确？

设贪心选择的第一个活动是 A，任意一个最优方案选择的第一个活动是 B。因为 A 是所有活动中结束最早的，所以 A 的结束时间不会晚于 B。

替换之后，活动数量没有减少，而且方案仍然合法。因此一定存在一个“第一步选择 A”的最优方案。对剩余活动重复同样的推理，贪心选择就能得到全局最优答案。这就是一个完整的交换论证。

用反例排除看似合理的策略

时间复杂度

时间复杂度描述输入规模 n 增大时，程序操作次数增长得有多快。它不直接等于运行秒数，而是帮助我们在写代码之前判断算法是否可能超时。

怎样从代码看出复杂度？

int answer = a[0] + a[n - 1];

for (int i = 0; i < n; i++)
    sum += a[i];

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        check(i, j);

四条推导规则

根据数据范围估计算法

空间复杂度

空间复杂度描述算法额外使用的存储空间怎样随输入规模增长。数组、容器、递归调用栈都会占用内存；超过题目的内存限制会得到 MLE。

把元素数量换算成内存

常见的 int 通常占 4 字节，long long 通常占 8 字节。估算数组内存时，可以使用：

别漏算这些空间

二分

二分利用单调性，每次检查中间位置并排除一半范围。本节分为两部分：二分查找在有序数组中寻找数值或边界；二分答案在可能的答案范围中寻找最优可行值。

01 · 二分查找

当数组已经有序时，可以通过比较 a[mid] 与目标值，排除不可能包含目标的一半元素。每次查询的时间复杂度为 O(log n)；如果需要先排序，还要另计 O(n log n) 的预处理时间。

示例：在有序数组中寻找 13

模板写法：统计小于、等于和大于目标值的个数

数组使用 1…n 下标。沿用模板的 calc(x) 与 calc2(x)：分别找到最后一个小于 x、最后一个小于等于 x 的位置。记为 y、z 后，三类元素个数依次是 y、z-y、n-z；判断 x 是否存在只需检查 z-y > 0。

输入 n、查询数 m、n 个数组元素，再输入 m 个目标值；每次输出“小于、等于、大于”的三个计数。数组先排序，每次查询做两次二分。

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

int n;
vector<int> a;

// 返回最后一个小于 x 的位置，也就是小于 x 的元素个数
int calc(int x) {
    int l = 0, r = n + 1;
    while (l + 1 < r) {
        int m = l + (r - l) / 2;
        if (a[m] < x) l = m;
        else r = m;
    }
    return l;
}

// 返回最后一个小于等于 x 的位置
int calc2(int x) {
    int l = 0, r = n + 1;
    while (l + 1 < r) {
        int m = l + (r - l) / 2;
        if (a[m] <= x) l = m;
        else r = m;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> n >> m;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin() + 1, a.end());
    while (m--) {
        int x;
        cin >> x;
        int y = calc(x), z = calc2(x);
        cout << y << ' ' << z - y << ' ' << n - z << '\n';
    }
    return 0;
}

竞赛更常用：寻找第一个满足条件的位置

同样使用模板的开区间写法：左端 l 是不满足条件的虚拟位置，右端 r 是满足条件的虚拟位置，只检查中间的真实位置。函数返回第一个 true；数组搜索时传入 l=0, r=n+1，返回 n+1 表示不存在，不能直接访问该位置。

template<class Check>
int firstTrue(int l, int r, Check check) { // 搜索开区间 (l, r)
    while (l + 1 < r) {
        int m = l + (r - l) / 2;
        if (check(m)) r = m; // r 维护满足条件的一侧
        else l = m;         // l 维护不满足条件的一侧
    }
    return r;
}

直接使用标准库边界函数

// a[1...n] 已经升序排序，不把 a[0] 作为搜索元素
bool found = binary_search(a.begin() + 1, a.end(), x);
auto it = lower_bound(a.begin() + 1, a.end(), x);
auto jt = upper_bound(a.begin() + 1, a.end(), x);

int pos = it == a.end() ? -1 : (int)(it - a.begin());
int cnt = (int)(jt - it); // 与 calc2(x) - calc(x) 相同

02 · 二分答案：把最优化变成判定

有些题没有一个已经排好序的数组，而是要求“最小的可行上限”或“最大的可行下限”。这时可以二分答案的数值：先猜一个 mid，再写 check(mid) 判断这个答案是否可行。

完整例题：最小化最大分组和

给定 n 个非负整数，在保持原顺序的前提下，把它们分成至多 k 个非空连续段，使所有段中最大的段和尽可能小。设 1 ≤ k ≤ n ≤ 2 × 10⁵，0 ≤ a[i] ≤ 10⁹。

为什么这个 check 正确？

固定上限后，因为元素非负，每段尽量向右延伸，只会给后面留下更短的后缀。任何合法分组的第一段都不能比贪心第一段更靠右；对剩下的后缀重复这个理由，就能说明贪心使用的段数最少。因此贪心都需要超过 k 段时，其余分法也做不到。存在负数时，这个贪心判定不再适用。

例如 a = [7, 2, 5, 10, 8]，k = 2：上限为 17 时需要 [7, 2, 5] | [10] | [8] 三段，不可行；上限为 18 时可以分成 [7, 2, 5] | [10, 8] 两段，所以最优答案为 18。

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

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

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    long long l = 0, r = 0;
    for (auto& x : a) {
        cin >> x;
        l = max(l, x); // 每个元素都必须放入某一段
        r += x;        // 整个数组作为一段一定可行
    }

    auto check = [&](long long mid) {
        int cnt = 1;
        long long sum = 0;
        for (long long x : a) {
            if (x > mid) return false;
            if (sum + x > mid) {
                ++cnt; // 当前段放不下，新开一段
                sum = x;
                if (cnt > k) return false;
            } else {
                sum += x;
            }
        }
        return true;
    };

    // 答案始终在闭区间 [l, r] 中，r 始终可行
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) r = mid; // mid 可行，继续尝试更小的上限
        else l = mid + 1;       // mid 不可行，更小的上限也不可行
    }
    cout << l << '\n';
    return 0;
}

二分查找与二分答案的区别

前缀和

如果需要反复询问数组某个区间的元素总和，每次从左到右重新累加会很慢。前缀和先进行一次 O(n) 预处理，之后每次区间查询只需 O(1)。

前缀和数组表示什么？

定义 s[i] 表示原数组前 i 个元素之和。为了让公式更整齐，令 s[0] = 0。

为什么区间公式成立？

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        // 前 r 项减去 l 之前的所有项
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}

二维前缀和

二维前缀和用于快速计算矩阵中的矩形区域和。它是一维前缀和的自然推广：s[i][j] 表示从左上角 (1, 1) 到右下角 (i, j) 的整个矩形元素之和。

怎样构造二维前缀和？

怎样查询任意矩形？

设矩形左上角为 (x1, y1)，右下角为 (x2, y2)，包含边界。先取右下角的大前缀矩形，再减去上方和左方多余区域，最后把被重复减去的左上区域加回来。

下面沿用模板中的 a、s 和 query。输入 n、m、q，再输入 n 行 m 列矩阵，每次询问输入 x1、y1、x2、y2。固定数组版本适用于 1 ≤ n,m ≤ 1000；更大范围需要同时调整 N 并检查内存。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1005;
ll a[N][N], s[N][N];
int n, m, q;

// 查询矩形 (x1, y1) ~ (x2, y2)，包含边界
ll query(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1 - 1][y2]
         - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            // 上方加左方，减掉重叠，再加当前位置
            s[i][j] = s[i - 1][j] + s[i][j - 1]
                    - s[i - 1][j - 1] + a[i][j];
        }
    }
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << query(x1, y1, x2, y2) << '\n';
    }
    return 0;
}

差分

如果要对数组的许多区间整体加上一个数，逐个修改区间中的每个元素会很慢。差分只修改区间的两个边界，每次操作是 O(1)，最后再用一次前缀和还原整个数组。

差分数组表示什么？

令 d[i] = a[i] - a[i - 1]，并规定 a[0] = 0。差分记录的是“当前位置相对前一个位置变化了多少”。

最后一个 0 是额外预留的 d[n + 1]，用于处理右端点恰好为 n 的区间修改。它不属于原数组。

区间 [l, r] 全部加上 k

完整模板：多次区间加

沿用模板“读入 a → 构造 d → 修改两个端点 → 还原 a”的顺序。原模板每次区间加 1；这里把增量读为 k，以覆盖已有例题中的正数和负数修改。第一行输入 n、q，每次操作输入 l、r、k。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    // 多留一格给 d[r+1]；long long 保存多次累加的结果
    vector<long long> a(n + 2), d(n + 2);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
    for (int i = 1; i <= q; i++) {
        int l, r;
        long long k;
        cin >> l >> r >> k;
        d[l] += k;
        d[r + 1] -= k;
    }
    // 对差分求前缀和，按模板还原到原数组 a
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + d[i];
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    cout << '\n';
    return 0;
}

5 2
3 1 4 1 5
2 4 2
1 3 -1

2 2 5 3 5

二维差分

二维差分可以把矩形 (c1, d1) 到 (c2, d2) 内的所有元素同时加上 k。沿用模板，原矩阵记为 a，二维差分记为 b；一次修改只改变四个角，最后用二维前缀和还原 a。

完整程序先输入 n、m、q 和 n 行 m 列初始矩阵；每次修改输入 c1、d1、c2、d2、k，最后输出修改后的矩阵。两个矩阵均额外预留一行一列，以处理右边界和下边界。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> a(n + 2, vector<long long>(m + 2));
    vector<vector<long long>> b(n + 2, vector<long long>(m + 2));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    // 用原矩阵构造二维差分
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] = a[i][j] - a[i][j - 1]
                    - a[i - 1][j] + a[i - 1][j - 1];
        }
    }
    while (q--) {
        int c1, d1, c2, d2;
        long long k;
        cin >> c1 >> d1 >> c2 >> d2 >> k;
        b[c1][d1] += k;
        b[c1][d2 + 1] -= k;
        b[c2 + 1][d1] -= k;
        b[c2 + 1][d2 + 1] += k;
    }
    // 按从上到下、从左到右的顺序还原 a
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = b[i][j] + a[i][j - 1]
                    + a[i - 1][j] - a[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

线性 DP

线性 DP 的状态按照数组下标、位置或时间从前向后排列。计算第 i 个状态时，只依赖已经算出的较小下标，因此可以按固定顺序递推。

什么时候可以考虑动态规划？

DP 五步法

例题：不相邻元素最大和

给定长度为 n（n ≥ 1）的整数数组，可以选择若干元素，但不能选择两个相邻元素。允许一个元素都不选，求所选元素之和的最大值。

先把样例递推出来

数组为 [2, 7, 9, 3, 1]。设 dp[0] = 0，逐个比较“选当前”和“不选当前”。

完整代码

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

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

    int n;
    cin >> n;

    // a[i] 是第 i 个位置的收益
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // dp[i] 表示前 i 个位置中，不选相邻位置的最大收益
    vector<long long> dp(n + 1, 0);
    dp[1] = max(0LL, a[1]);

    for (int i = 2; i <= n; i++) {
        // 不选 i，或选 i 并跳过 i-1
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
    }

    cout << dp[n] << '\n';
    return 0;
}

5
2 7 9 3 1

12

空间为什么可以优化到 O(1)？

计算 dp[i] 时只使用 dp[i-1] 和 dp[i-2]，更早的状态不会再次使用，因此只需保存最近两个值。

long long x = 0;                 // dp[i - 2]
long long y = max(0LL, a[1]); // dp[i - 1]

for (int i = 2; i <= n; i++) {
    // 先算新状态，再依次移动前两个状态
    long long z = max(y, x + a[i]);
    x = y;
    y = z;
}

两种常见的线性状态定义

XCPC 模板中的最长上升子序列

沿用XCPC 模板命名：a[i] 保存第 i 个数，f[i] 表示必须以 a[i] 结尾的最长严格上升子序列长度。先令 f[i] = 1，再枚举所有 j < i，只在 a[i] > a[j] 时接到 j 后面。答案是所有 f[i] 的最大值，不能直接输出 f[n]；相等元素不能延长严格上升序列。

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

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

    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        f[i] = 1;  // 只选 a[i]，长度至少为 1
        for (int j = 1; j < i; j++) {
            if (a[i] > a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(f[i], ans);
    cout << ans << '\n';
    return 0;
}

时间复杂度 O(n²)，空间复杂度 O(n)；与模板相同采用二重循环，先结合 n 的范围判断能否通过。

XCPC 模板中的最长公共子序列

输入两列整数，长度分别为 n、m。f[i][j] 表示 a 的前 i 个数与 b 的前 j 个数的最长公共子序列长度。先考虑跳过任意一列末尾的数；若 a[i] == b[j]，还可以把这两个数接在 f[i-1][j-1] 后。空前缀所在的第 0 行与第 0 列均为 0。

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

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) {
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    cout << f[n][m] << '\n';
    return 0;
}

时间与空间复杂度均为 O(nm)。这两个模板补充了“以 i 结尾”与“两个前缀”的状态；前面的不相邻元素例题仍用于讲解 DP 入门与滚动优化。

线性 DP 常见错误

背包 DP

背包问题研究“若干物品 + 一个容量限制 + 如何选择物品”。真正需要掌握的不是模板本身，而是状态表示、物品使用次数以及容量为什么要按特定方向遍历。

0/1 背包模型

输入顺序按XCPC 模板保留：0/1 背包先读 m n，完全背包先读 n m；每件物品都读 v[i] w[i]。下面分别注明，复制时按对应格式输入。

有 n 件物品，第 i 件物品体积为 v[i]、价值为 w[i]，背包容量为 m。沿用XCPC 模板，v 表示占用容量，w 表示价值。每件物品只能选择 0 次或 1 次，求总体积不超过 m 时的最大总价值。

从两种决策推导转移

当 j < v[i] 时装不下当前物品，只能不选；否则在两种决策中取最大值：

手算一张 DP 表

容量 m = 8，四件物品分别为 (体积, 价值) = (2,3)、(3,4)、(4,5)、(5,8)。每处理一件物品，就用上一行更新当前行。

最终 f[4][8] = 12，对应选择体积 3、价值 4 的物品和体积 5、价值 8 的物品。

二维写法：最容易理解

// f[i][j]：前 i 件物品、容量不超过 j 时的最大价值
vector<vector<long long>> f(
    n + 1, vector<long long>(m + 1, 0)
);

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i - 1][j];  // 不选第 i 件物品

        // 容量足够时，再尝试选择第 i 件物品
        if (j >= v[i]) {
            f[i][j] = max(
                f[i][j],
                f[i - 1][j - v[i]] + w[i]
            );
        }
    }
}

压缩成一维：容量必须倒序

第 i 行只依赖第 i - 1 行，可以复用同一个 f[j] 数组。为了让右侧的 f[j-v[i]] 仍然代表“没有处理当前物品”的旧值，容量必须从大到小更新。

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

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

    int n, m;
    cin >> m >> n;  // 与模板一致：先容量，再物品数
    vector<int> v(n + 1);
    vector<long long> w(n + 1), f(m + 1, 0);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        // 倒序枚举容量，保证每件物品只用一次
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << '\n';
    return 0;
}

8 4
2 3
3 4
4 5
5 8

12

为什么正序会错？

假设只有一件体积 2、价值 3 的物品，容量为 6。如果容量从小到大更新：

完全背包：同一件物品可以重复使用

完全背包仍可使用一维 f[j]，但容量从小到大更新。这样 f[j-v[i]] 可能已经在本轮加入当前物品，继续转移正好表示再次选择它。

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

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

    int n, m;
    cin >> n >> m;  // 完全背包模板：先物品数，再容量
    vector<int> v(n + 1);
    vector<long long> w(n + 1), f(m + 1, 0);
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        // 正序枚举容量，允许当前物品重复使用
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << '\n';
    return 0;
}

“不超过容量”与“恰好装满”初始化不同

// NEG 表示不可达，只有容量 0 的初始状态可达
const long long NEG = -(1LL << 60);
vector<long long> f(m + 1, NEG);
f[0] = 0;

// 转移时只有来源可达，才能继续选择物品。
if (j >= v[i] && f[j - v[i]] != NEG) {
    f[j] = max(f[j], f[j - v[i]] + w[i]);
}

数据范围决定能不能使用背包 DP

树形 DP

在线性 DP 中，我们沿着数组从左到右计算；到了树上，节点会同时分出多个方向，应该先算谁就不再显然。树形 DP 做的第一件事，就是把无向的树整理成“父亲依赖儿子”的计算结构，再把每棵小子树的答案一层层向上合并。

第一步：把树“有根化”

如果输入直接说明“父亲是谁”，可以只保存父亲到儿子的有向边；如果输入只是 n - 1 条无向边，就要双向加边，并在 DFS 中跳过父亲。无根树在题目没有特殊要求时通常可任选 1 号节点为根。

vector<vector<int>> q;  // 在读入 n 后初始化为 n + 1 个邻接表

void solve(int u, int fa) {
    // 1. 初始化 f[u]
    for (int v : q[u]) {
        if (v == fa) continue;
        solve(v, u);
        // 2. 使用已经算好的 f[v] 更新 f[u]
    }
}

程序向下走，答案向上长

这是初学树形 DP 最容易混淆的一点。调用 solve(1, 0) 时，程序先进入 1，再进入 2、4；但 4 没有儿子，会最先完成状态。回到 2 后继续完成 5，等 4、5 都算完，2 才能合并它们。

入门状态：求每个节点的子树大小

定义 f[u] 为“以 u 为根的子树节点数”。初始化时 u 自己贡献 1；每完成一个儿子 v，就把 f[v] 加到 u。于是：

为什么这里可以直接相加？

以 u 的不同儿子为根的子树互不重叠：一个节点不可能同时属于两个儿子的子树。因此，u 的子树可以被完整拆成“u 自己 + 每个儿子的子树”，既没有遗漏，也不会重复计算。

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

int n;
vector<int> f;
vector<vector<int>> q;

void solve(int i, int fa) {
    f[i] = 1;  // 节点自己占 1 个位置
    for (auto j : q[i]) {
        if (j == fa) continue;  // 无向边会通回父亲，必须跳过
        solve(j, i);
        f[i] += f[j];  // 儿子的子树算完后再合并
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    f.assign(n + 1, 0);
    q.resize(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        q[x].push_back(y);
        q[y].push_back(x);
    }
    solve(1, 0);
    for (int i = 1; i <= n; i++) cout << f[i] << (i == n ? '\n' : ' ');
    return 0;
}

5
1 2
1 3
2 4
2 5

5 3 1 1 1

经典模型：没有上司的舞会

每位员工 u 有快乐值 v[u]。如果 u 参加舞会，u 的直接下属不能参加；求整棵公司树能获得的最大快乐值。父亲能否选择某个儿子，取决于父亲自己是否参加，因此一个状态不够。

只讨论一个儿子，转移就会自己出现

先暂时忘掉整棵树，只看相邻的父亲 u 和儿子 v。父亲不参加时没有给 v 施加限制，v 可以在自己的两种状态里选较大的；父亲参加时，为避免相邻两人同时出现，v 只能不参加。

手算一次“儿子 → 父亲”

继续使用开头那棵树，节点 1—5 的快乐值分别是 5、4、3、6、2。把状态写成二元组 (不参加, 参加)，严格按照 4、5、2、3、1 的顺序计算：

完整代码：输入给出下属与上司

下面约定每行 u v 表示 v 是 u 的直接上司。建边时使用 q[v].push_back(u)，并用 fa 沿上司链找到真正的根，不能默认根一定是 1。

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

int n;
vector<long long> v;
vector<int> fa;
vector<array<long long, 2>> f;
vector<vector<int>> q;

void solve(int u) {
    f[u][0] = 0;
    f[u][1] = v[u];
    for (auto son : q[u]) {
        solve(son);
        f[u][0] += max(f[son][0], f[son][1]);
        f[u][1] += f[son][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    v.resize(n + 1);
    fa.assign(n + 1, 0);
    f.assign(n + 1, {0, 0});
    q.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;  // y 是 x 的上司
        q[y].push_back(x);
        fa[x] = y;
    }
    int root = 1;
    while (fa[root]) root = fa[root];
    solve(root);
    cout << max(f[root][0], f[root][1]) << '\n';
    return 0;
}

5
5 4 3 6 2
2 1
3 1
4 2
5 2

13

把完整代码拆回四个问题

当题目再增加人数限制：树形背包

普通舞会只关心“选不选 i”。如果再要求最多选择 m 个人，父亲合并儿子时还必须知道每棵子树分到几个名额。这里按XCPC 模板，把人数这一维定义为容量上限。

先把 j、k、j-k 翻译成人话

j、k 是人数上限，可以有空余，不要求必须用满。合并一个儿子时，i 不参加便可取儿子的两种状态的最大值；i 参加则只能取儿子不参加的状态。k = 0 的情况就是保留旧值，因此代码从 k = 1 开始。

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

int n, m;
const long long NEG = -(1LL << 60);
vector<long long> v;
vector<int> fa;
vector<vector<int>> q;
vector<vector<array<long long, 2>>> f;

void solve(int i) {
    // 此时两列都只合并儿子的贡献，i 自己最后才占名额。
    for (auto son : q[i]) {
        solve(son);
        for (int j = m; j >= 0; j--) {
            for (int k = 1; k <= j; k++) {
                f[i][j][0] = max(f[i][j][0],
                    f[i][j - k][0] + max(f[son][k][0], f[son][k][1]));
                f[i][j][1] = max(f[i][j][1],
                    f[i][j - k][1] + f[son][k][0]);
            }
        }
    }
    // i 参加：预留一个名额给自己，其他名额只允许儿子不参加。
    for (int j = m; j >= 1; j--) f[i][j][1] = f[i][j - 1][1] + v[i];
    f[i][0][1] = NEG;  // 0 个名额不能让 i 参加
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    v.resize(n + 1);
    q.resize(n + 1);
    fa.assign(n + 1, 0);
    f.assign(n + 1, vector<array<long long, 2>>(m + 1, {0, 0}));
    // 沿用人数限制模板的输入顺序，同时记录父亲找实际根。
    for (int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;  // y 是 x 的上司
        q[y].push_back(x);
        fa[x] = y;
    }
    for (int i = 1; i <= n; i++) cin >> v[i];
    int root = 1;
    while (fa[root]) root = fa[root];
    solve(root);
    cout << max(f[root][m][0], f[root][m][1]) << '\n';
    return 0;
}

输入格式沿用人数限制模板：第一行 n m，接着 n - 1 行 x y 表示 y 是 x 的上司；代码通过 fa 找根，最后输入 n 个快乐值。与上面的普通舞会程序相比，快乐值与边的读取顺序不同。

例如最多选 2 人时，选 1 与 4 可得 11；最多选 3 人时，选 1、4、5 可得 13。因为允许少选，负快乐值的员工可以不选。直接三重合并上界为 O(nm²)，空间为 O(nm)。

树形 DP 的固定思考流程

看到什么题意，应该想到哪种状态？

按难度完成三次练习

换根 DP

树形 DP 通常先选定一个根，只计算这个根对应的答案；但有些题会追问“如果 1、2、3……每个节点分别作为根，答案是多少”。换根 DP 不会从每个节点重新跑一遍，而是先求出一个根的答案，再沿着每条边把已经算好的信息传给相邻节点。

经典问题：每个点到所有节点的距离和

给定一棵 n 个节点的无权树，定义 ans[x] 为节点 x 到所有节点的距离之和。我们需要输出 ans[1..n]。例如下面这棵树，边为 1-2、1-3、2-4、2-5：

先固定 1 为根，定义两个量

变量沿用XCPC 模板：q 保存邻接表，s 是子树大小，f 是子树内距离和，v 是子树外距离和，b 是访问标记；up 自底向上收集，down 自顶向下转移。下文用 x、y 表示父子节点，避免与数组 v 混淆。

一个儿子 y 怎样贡献给父亲 x？

f[y] 已经统计了 y 到它子树中所有节点的距离。现在起点从 y 移到父亲 x，每条路径都多经过边 x-y，而 y 子树共有 s[y] 个节点，所以统一增加 s[y]。

在示例树上从叶子往上算

节点 2 收到叶子 4、5 的贡献：f[2] = (0 + 1) + (0 + 1) = 2。节点 1 再收到 2 和 3：f[1] = (2 + 3) + (0 + 1) = 6。因为 1 的子树就是整棵树，所以 ans[1] = f[1]。

void up(int i) {
    s[i] = 1;
    b[i] = true;
    for (auto j : q[i]) {
        if (!b[j]) {
            up(j);
            s[i] += s[j];
            f[i] += f[j];
        }
    }
    // 每个后代到 i 都比到其所属儿子多走 1 条边。
    f[i] += s[i] - 1;
}

模板把各儿子的 f[j] 先相加，最后统一增加 s[i] - 1。因为 s[i] - 1 = Σ s[j]，这与逐个儿子累加 f[j] + s[j] 完全等价。

从父亲 x 换到儿子 y，所有点恰好分成两组

手算根从 1 移到 2

继续把根从 2 移到叶子 4：ans[4] = 5 + 5 - 2 × 1 = 8。同理可以得到所有节点的答案：

void down(int i) {
    b[i] = true;
    for (auto j : q[i]) {
        if (!b[j]) {
            // 父亲整树贡献 - 儿子子树旧贡献 + 子树外每点远 1。
            v[j] = f[i] + v[i] - s[j] - f[j] + n - s[j];
            down(j);
        }
    }
}

如果直接公式显得跳跃，可以先定义 v[x]：从 x 到其子树之外所有节点的距离和。于是 ans[x] = f[x] + v[x]。对于 x 的儿子 y：

把两次 DFS 连起来

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

int n;
vector<ll> f, v;
vector<int> s;
vector<bool> b;
vector<vector<int>> q;

void makelist(int x, int y) {
    q[x].push_back(y);
    q[y].push_back(x);
}

void up(int i) {
    s[i] = 1;
    b[i] = true;
    for (auto j : q[i]) {
        if (!b[j]) {
            up(j);
            s[i] += s[j];
            f[i] += f[j];
        }
    }
    // 每个后代到 i 都比到其所属儿子多走 1 条边。
    f[i] += s[i] - 1;
}

void down(int i) {
    b[i] = true;
    for (auto j : q[i]) {
        if (!b[j]) {
            // 父亲整树贡献 - 儿子子树旧贡献 + 子树外每点远 1。
            v[j] = f[i] + v[i] - s[j] - f[j] + n - s[j];
            down(j);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    q.resize(n + 1);
    s.assign(n + 1, 0);
    f.assign(n + 1, 0);
    v.assign(n + 1, 0);
    b.assign(n + 1, false);
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        makelist(x, y);
    }
    up(1);
    fill(b.begin(), b.end(), false);  // 第二遍遍历前清空访问标记
    down(1);                       // v[1] = 0，根没有子树外节点
    for (int i = 1; i <= n; i++) cout << f[i] + v[i] << '\n';
    return 0;
}

换根 DP 的固定思考流程

带权边只是把“变化 1”换成“变化 w”

若边 x-y 的权值为 w，根移过这条边后，y 子树内每个节点的距离减少 w，子树外每个节点的距离增加 w：

按难度完成三次练习

区间 DP

线性 DP 常用一个下标表示“处理到哪里”，区间 DP 则同时记录左右端点，用 f[l][r] 描述连续区间 [l, r]。它最重要的不是三层循环，而是弄清：一个长区间的最后一步，怎样由更短的区间组成。

f[l][r] 到底比 f[i] 多记录了什么？

长度为 len、左端点为 l 时，右端点不是另一个独立循环变量，而是由区间长度唯一确定：

for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;

        // 此时计算区间 [l, r]
        // 它依赖的更短区间已经算完
    }
}

区间 DP 的两条主路线

题目模型

n 堆石子排成一行，每次只能把相邻两堆合并，代价等于两堆石子的总数。要求把所有石子合成一堆的最小总代价。对于 1、2、10：

不要从“第一步合并什么”想，要从“最后一步剩什么”想

当 [l,r] 最终合成一堆时，最后一次合并之前一定恰好剩下两堆连续石子。它们可以写成 [l,k] 和 [k+1,r]，其中 k 从 l 枚举到 r-1。

用前缀和 O(1) 求区间石子总数

按XCPC 模板，状态数组统一写成 f；公式仍用 l、r 讲解区间，代码中用 i 表示长度、j 表示左端点，所以 l = j、r = j + i - 1，k 仍是分界点。

如果每次转移都重新循环求 sum(l,r)，会在三层枚举外又增加一层计算。前缀和让区间代价保持 O(1)。

四堆石子 1、2、10、4 的完整填表

计算 f[1][4] 时，区间总和固定为 17，但最后分成哪两段并不固定。把三个候选方案真正代入：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n + 1), s(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    const long long INF = (1LL << 60);
    vector<vector<long long>> f(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) f[i][i] = 0;

    // i 枚举区间长度，j 枚举左端点。
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j + i - 1 <= n; j++) {
            // 枚举最后一次合并的分界 k。
            for (int k = j; k <= j + i - 2; k++) {
                f[j][j + i - 1] = min(f[j][j + i - 1],
                    f[j][k] + f[k + 1][j + i - 1] + s[j + i - 1] - s[j - 1]);
            }
        }
    }
    cout << f[1][n] << '\n';
    return 0;
}

这次状态求的是最大值

括号模板也沿用 i、j、k 的枚举方式。字符串没有补空格，区间 [j,j+i-1] 的字符下标要分别减 1；f 多开两格，使长度为 2 时访问空区间仍合法。

给定只含 ( ) [ ] 的字符串，求最长合法括号子序列长度。子序列允许跳过字符，但不能改变相对顺序。例如 ([)] 不是合法括号串，却能选择 () 或 []，答案为 2。

情况一：左右端点恰好能配成一对

如果区间的左右端字符是 () 或 []，可以把它们包在中间最优解两侧。DP 区间用 1-based 下标，代码里的字符串保留 0-based，因此 [l,r] 对应 s[l-1] 与 s[r-1]：

情况二：答案由两个合法子序列拼接

合法序列还可能像 (())[] 一样由两段组成，因此仍要枚举分界点 k：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));

    // DP 用 1-based 区间，字符串 s 保留 0-based 下标。
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j + i - 1 <= n; j++) {
            // 区间 [j,j+i-1] 的两个字符是 s[j-1]、s[j+i-2]。
            if ((s[j - 1] == '[' && s[j + i - 2] == ']') ||
                (s[j - 1] == '(' && s[j + i - 2] == ')')) {
                f[j][j + i - 1] = f[j + 1][j + i - 2] + 2;
            }
            // 即使端点可配对，也要继续考虑分割。
            for (int k = j; k <= j + i - 2; k++) {
                f[j][j + i - 1] = max(f[j][j + i - 1],
                    f[j][k] + f[k + 1][j + i - 1]);
            }
        }
    }
    cout << f[1][n] << '\n';
    return 0;
}

初始化不是选择一种 memset，而是代入状态定义

动笔前固定回答六个问题

按难度完成三次练习