K06 动态规划一：一维 DP 与背包（第二轮系统课 · 第 6 次）

本次课 3 小时：前 45 分钟复盘 10/10 的整卷①，然后是本模块。

〇、整卷①复盘（课上前 45 分钟）

带着 S9 的复盘表来。老师只问三件事：

1. 四道题各用了多少分钟？哪一道超了计划时间还没停？
2. T3、T4 有没有写暴力？写了拿到几分？
3. 有没有因为文件名、freopen、格式丢分的？

一、M11 动态规划一

盲写（15 分钟，合上讲义）

01 背包：输入背包容量 T 和物品数 m（T ≤ 1000，m ≤ 100），接下来 m 行每行一个物品的重量和价值。每个物品最多拿一次，求总重量不超过 T 时的最大总价值。用一维数组写。

输入 70 3 / 71 100 / 69 1 / 1 2 → 输出 3

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

int f[1005];                  // f[j]：容量为 j 时的最大价值（全局，自动为 0）

int main() {
    int T, m;
    cin >> T >> m;
    for (int i = 1; i <= m; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = T; j >= w; j--)          // 01 背包：倒序
            f[j] = max(f[j], f[j - w] + v);
    }
    cout << f[T] << endl;
    return 0;
}

写对了 → 看 1.2 起。写不出，或者内层写成了正序 → 先读 L05 采药那一节（二维怎么压成一维、为什么倒序）。

1.1 复用

1.2 一维 DP 的两种状态设计

拿到一道序列上的 DP 题，状态几乎总是下面两种之一：

⚠️ "以 i 结尾"的答案不是 f[n]，因为最优的那一段不一定以最后一个元素结尾。这是这类题最常见的错。

1.3 最长上升子序列（LIS）

从序列里挑出一些数（不必连续，但顺序不变），使它们严格递增，最长能挑几个？

三件套：

1. 状态：f[i] = 以 a[i] 结尾的最长上升子序列长度
2. 转移：看 a[i] 能接在谁后面——对所有 j < i 且 a[j] < a[i]，f[i] = max(f[j] + 1)
3. 初始：每个数自己就是长度 1，f[i] 初值为 1

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

int a[5005], f[5005];

int main() {
    int n;
    cin >> n;
    // n<=5000，O(n^2)=2.5e7，能过
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = 1;                                   // 初始：自己一个
        for (int j = 1; j < i; j++)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);                       // 答案是所有 f[i] 的最大值
    }
    cout << ans << endl;
    return 0;
}

📝 变形只改一个符号：最长不下降（可以相等）把 < 改成 <=；最长下降改成 >。读题时圈出"严格"两个字。

⚠️ n 到 10⁵ 时 O(n²) 就超时了，要 O(n log n) 的做法（二分），那属于提高内容。n ≤ 10⁵ 的 LIS 题，O(n²) 能拿 n ≤ 5000 那几档部分分——K01 讲的"数据范围告诉你暴力能拿几分"。

1.4 完全背包

每种物品可以拿无限次。 和 01 背包的代码只差一个循环方向：

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

long long f[100005];

int main() {
    int T, m;
    cin >> T >> m;
    for (int i = 1; i <= m; i++) {
        int w, v;
        cin >> w >> v;
        for (int j = w; j <= T; j++)            // 完全背包：正序
            f[j] = max(f[j], f[j - w] + v);
    }
    cout << f[T] << endl;
    return 0;
}

📝 为什么正序就是"可以拿无限次"：正序时，算 f[j] 用到的 f[j - w] 已经是这一轮更新过的——它里面可能已经放了一个物品 i，再加一个就是放了两个。倒序时 f[j - w] 还是上一轮的，所以物品 i 最多放一次。

同一组数据，01 背包答案 3，完全背包答案 140（拿 70 个重量 1、价值 2 的物品）。L05 说"正序会输出 140"，就是这个。

⚠️ 价值总和可能很大，f 用 long long。课堂题 P1616 疯狂的采药不开 long long 会错。

1.5 方案数和"恰好装满"

为什么"恰好装满"要把初值设成负无穷：f[j] 初值 0 等于在说"容量 j 什么都不放也行"。恰好装满时这不合法，用负无穷表示"这个状态不存在"，它加上什么都还是很小，不会被选中。

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

int f[10005];

int main() {
    // 方案数：用若干个数（每个最多用一次）凑出恰好 M 的方法数
    int n, M;
    cin >> n >> M;
    f[0] = 1;                                  // 凑出 0：什么都不选，1 种
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        for (int j = M; j >= a; j--) f[j] += f[j - a];   // 每个数只能用一次：倒序
    }
    cout << f[M] << endl;
    return 0;
}

📝 这就是作业 P1164 小 A 点菜。

1.6 DP 写错了怎么查

1. 把 f 数组打印出来，和手算的表对照。 数字三角形、背包都可以在纸上画 3×5 的小表。
2. 检查初值：是 0、是 1、还是负无穷？和 1.5 那张表对一下。
3. 检查答案位置："以 i 结尾"要取最大值，"前 i 个"取 f[n]。
4. 检查循环方向：01 倒序、完全正序。
5. 检查 long long。

二、课堂题

三、本周作业（10/12–10/16，每天 1 道）

10/17（六）08:30–12:00 整卷② NOIP2016 普及组，规矩同 F0 第四节。

四、30 秒自测

1. "以 i 结尾"和"前 i 个"两种状态，答案分别在哪？
2. LIS 的转移方程？初值？
3. 01 背包和完全背包的代码差在哪？为什么？
4. "恰好装满"和"不超过"的初值有什么不同？
5. 方案数背包的 f[0] 为什么是 1？

本次打卡：M11 ①（盲写）；作业 AC 后打 ②③。