书本整理

GitHub跳转原题关系图返回列表

按高度排序后，设 `dp[i][j]` 为保留 i 本且最后一本是第 j 本时的最小不整齐度，枚举上一本转移。

OJ: luogu

题目 ID: P1103

难度:普及/提高-

标签:动态规划排序

日期: 2026-06-19 12:07

目录

  1. 题意
  2. 思路
    1. 状态表
    2. DP 公式
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

每本书有高度和宽度。

先把所有书按高度从小到大放到书架上，然后删去恰好 k 本书。

剩余书本的不整齐度定义为：相邻保留书本宽度差绝对值之和。

要求最小化这个不整齐度。

思路

最直接的想法是暴力枚举保留哪些书。

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：小数据暴力解，使用 01 序列枚举每本书保留或删除。

const int MAXN = 25;
const int INF = 1000000000;

struct Book {
    int h, w;
};

int n, k;
Book a[MAXN];
int keep_cnt;
int keep_book[MAXN]; // keep_book[i] = 0/1，表示第 i 本书删除/保留
int ans;

bool cmp_book(const Book &lhs, const Book &rhs) {
    return lhs.h < rhs.h;
}

int calc_keep_count() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (keep_book[i] == 1) cnt++;
    }
    return cnt;
}

bool check() {
    return calc_keep_count() == keep_cnt;
}

int calc_answer() {
    int last = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (keep_book[i] == 0) continue;
        if (last != 0) {
            sum += abs(a[i].w - a[last].w);
        }
        last = i;
    }
    return sum;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (ans > value) ans = value;
        }
        return;
    }

    // 第 dep 本书的 01 选择：0 删除，1 保留。
    for (int i = 0; i <= 1; i++) {
        keep_book[dep] = i;
        dfs_choose(dep + 1);
    }
}

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, cmp_book);

    keep_cnt = n - k;
    ans = INF;
    dfs_choose(1);

    cout << ans << '\n';
    return 0;
}

brute.cpp 会先按高度排序，再把每本书看成一个 01 选择：keep_book[i] = 0/1 表示删除或保留。递归先生成完整选择，叶子节点再检查是否正好保留 n-k 本，并计算相邻宽度差之和。

这个做法很直观，但组合数太大，不能用于正式数据。

接下来考虑 DP。

由于书一定要先按高度排序，所以我们可以先把所有书按 h 从小到大排好。 排序以后，问题就变成：

从这个序列里选出 n-k 本书，使相邻保留元素的宽度差绝对值总和最小。

设：

dp[i][j] = 保留 i 本书，且第 i 本保留书是排序后第 j 本书时的最小不整齐度

如果当前最后一本保留书是 j，那么上一本保留书一定是某个 p < j。

于是转移是：

dp[i][j] = min(dp[i-1][p] + abs(w[j] - w[p]))

状态表

样例排序后其实顺序不变，宽度依次为：

2, 4, 1, 3

要删掉 1 本，所以保留 3 本。

关键状态如下：

保留本数 最后一本位置 最优值
1 任意 j 0
2 2 $
2 3 $min(
2 4 $min(
3 3 3
3 4 3

所以最终答案是 3。

DP 公式

排序后，设 need=n−kneed=n-k 为最终要保留的书本数量。令 dpi,jdp_{i,j} 表示保留 ii 本书，且第 ii 本保留书是排序后第 jj 本时的最小不整齐度。初始化：

dp1,j=0 dp_{1,j}=0

当 p<jp<j 时，可以把第 jj 本接在第 pp 本后面：

dpi,j=min⁡p<j(dpi−1,p+∣wj−wp∣) dp_{i,j}=\min_{p<j}\left(dp_{i-1,p}+|w_j-w_p|\right)

最终答案为：

min⁡jdpneed,j \min_j dp_{need,j}

公式解释：排序后，保留书本的相对顺序已经固定。若第 i 本保留书是第 j 本原书，那么上一本文只能来自某个 p<j，代价增加相邻两本宽度差的绝对值。

代码

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

const int MAXN = 105;
const int INF = 1000000000;

struct Book {
    int h, w;
};

int n, k;
Book a[MAXN];
int dp[MAXN][MAXN];

bool cmp_book(const Book &lhs, const Book &rhs) {
    return lhs.h < rhs.h;
}

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, cmp_book);

    int keep = n - k;

    for (int i = 0; i <= keep; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = INF;
        }
    }

    // 只保留一本书时，不整齐度为 0。
    for (int j = 1; j <= n; j++) {
        dp[1][j] = 0;
    }

    for (int cnt = 2; cnt <= keep; cnt++) {
        for (int j = cnt; j <= n; j++) {
            for (int p = cnt - 1; p < j; p++) {
                dp[cnt][j] = min(dp[cnt][j], dp[cnt - 1][p] + abs(a[j].w - a[p].w));
            }
        }
    }

    int ans = INF;
    for (int j = keep; j <= n; j++) {
        ans = min(ans, dp[keep][j]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O((n−k)∗n2)O((n-k) * n^2)
  • 空间复杂度：O((n−k)∗n)O((n-k) * n)

总结

这题的关键是先按高度排序，把二维的“高宽”问题变成一维序列选择。

之后用“保留了多少本、最后一本是谁”来设计状态，转移就非常直接。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析