P1103《书本整理》精讲
不東工作室 · P1103《书本整理》精讲
（洛谷原题）
────────────────────
"'
讲这个题？
因为最近小学/中学生c++竞赛压力蛮大的,做一些讲解，可能是他们做题的时候比较轻松
——不东工作室
"'
一、题意再述（适合小学生阅读版）
有 n 本书，每本书只有“高度”和“宽度”两个数字。
1. 先把书按高度从小到大排好（因为高度都不同，不会打架）。
2. 现在我们要从里面拿走恰好 k 本，只留下 n-k 本。
3. 留下的书仍要保持“高度有序”。
4. 把留下的书一本挨一本放在书架上，定义“不整齐度”：
相邻两本书的宽度差的绝对值，全部加起来。
目标：在所有拿 k 本的方案里，让“不整齐度”最小。
────────────────────
二、思路精讲（一步一步拆）
1. 先按高度排序
因为高度两两不同，直接 `sort` 就行。
2. 发现“留下书”一定是原序列的一段“子序列”
只要保持原来高度递增即可。
3. 状态设计
设 f[i][j] 表示：
“已经看到第 i 本书，已经留下 j 本书，且最后一本留下的是第 i 本”
时的最小不整齐度。
4. 转移方程
对于第 i 本书，枚举上一本留下的书 t（t < i）：
cost = |w[i] - w[t]|
f[i][j] = min(f[i][j], f[t][j-1] + cost)
5. 边界
当 j == 1（只留 1 本）时，不整齐度为 0。
6. 答案
在 f[i][n-k] 中取最小值。
7. 复杂度
状态 O(n²)，转移 O(n) → O(n³)
n ≤ 100，100³ = 1e6，1 秒内轻松通过。
────────────────────
三、易错示范 + 逐行注释（给同学们找茬用）
错误示范 1：把“子序列”当成“连续区间”
// 错误点：用滑动窗口，只删连续 k 本
for (int l = 0; l < n - k; ++l) {int r = l + (n - k) - 1;int sum = 0;for (int i = l + 1; i <= r; ++i)sum += abs(w[i] - w[i - 1]);ans = min(ans, sum);
}- 错因：题目允许“跳着删”，连续区间只是子集，答案必然偏大。
错误示范 2：贪心选“相邻差最小”的删
vector<int> diff(n - 1);
for (int i = 0; i < n - 1; ++i)diff[i] = abs(w[i + 1] - w[i]);
sort(diff.begin(), diff.end());
long long ans = 0;
for (int i = 0; i < n - k - 1; ++i)ans += diff[i];
- 错因：删掉一本书会同时影响左右两个差值，贪心无法保证全局最优。
错误示范 3：DP 下标从 1 开始却用 0 初始化
memset(f, 0x3f, sizeof(f)); // 正确
// 错误：memset(f, 0, sizeof(f)); 导致全 0 起点，答案偏小─────────────────
四、AC 代码 + 逐行讲解（可直接抄到洛谷/编译器）
#include <bits/stdc++.h>
using namespace std;const int MAXN = 105;
const int INF = 0x3f3f3f3f;struct Book {int h, w;bool operator < (const Book& o) const {return h < o.h; // 按高度升序}
} a[MAXN];int n, k;
int f[MAXN][MAXN]; // f[i][j]: 前i本选j本，最后一本是i的最小代价int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> k;for (int i = 1; i <= n; ++i)cin >> a[i].h >> a[i].w;sort(a + 1, a + n + 1); // 步骤1：按高度排序memset(f, 0x3f, sizeof(f));for (int i = 1; i <= n; ++i)f[i][1] = 0; // 只选1本，不整齐度为0for (int j = 2; j <= n - k; ++j) // j：已选书的本数for (int i = j; i <= n; ++i) // i：最后一本书编号for (int t = j - 1; t < i; ++t) // t：倒数第二本书编号f[i][j] = min(f[i][j],f[t][j - 1] + abs(a[i].w - a[t].w));int ans = INF;for (int i = n - k; i <= n; ++i)ans = min(ans, f[i][n - k]); // 最后一本可以是任意一本cout << ans << endl;return 0;
}祝不東的读者们AC！