[ICPC 2001 Taejon R] 木棍加工

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

先按长度降序、同长度按宽度降序排序，再在宽度序列上求最长严格上升子序列长度，它等于最少需要开的加工链数。

OJ: luogu

题目 ID: P1233

难度:普及/提高-

标签:动态规划排序lisDilworth定理

日期: 2026-06-19 12:53

目录

  1. 题意
  2. 思路
    1. 样例排序后
    2. DP 公式
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有 n 根木棍，每根木棍有长度和宽度。

如果当前刚加工完的木棍长宽分别不小于下一根，那么下一根就不需要新的准备时间；否则要多花 1 分钟准备。

问怎样安排加工顺序，才能让总准备时间最少。

思路

先看最直接的暴力做法：

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

// brute.cpp：小数据回溯枚举每根木棍放到哪条加工链中，求最少链数。

const int MAXN = 18;

struct Stick {
    int l, w;
};

int n;
Stick a[MAXN];
Stick tail[MAXN]; // 每条当前加工链最后一根木棍
int chain_cnt;
int ans;

bool can_follow(const Stick &last, const Stick &cur) {
    return last.l >= cur.l && last.w >= cur.w;
}

bool cmp_stick(const Stick &x, const Stick &y) {
    if (x.l != y.l) {
        return x.l > y.l;
    }
    return x.w > y.w;
}

void dfs(int idx) {
    if (chain_cnt >= ans) {
        return;
    }
    if (idx > n) {
        ans = min(ans, chain_cnt);
        return;
    }

    Stick cur = a[idx];

    for (int i = 1; i <= chain_cnt; i++) {
        if (can_follow(tail[i], cur)) {
            Stick old = tail[i];
            tail[i] = cur;
            dfs(idx + 1);
            tail[i] = old;
        }
    }

    chain_cnt++;
    tail[chain_cnt] = cur;
    dfs(idx + 1);
    chain_cnt--;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].w;
    }

    // 先排序，把“任意重排后分链”的问题转成固定顺序下的最小链覆盖。
    sort(a + 1, a + n + 1, cmp_stick);

    ans = n;
    chain_cnt = 0;
    dfs(1);

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

brute.cpp 会先按同样的排序规则整理木棍，再把每根木棍尝试放到某条已有加工链后面，或者新开一条链，最后求最少链数。
因为每开一条新链，就对应一次新的准备时间，所以这和原题是等价的。

但暴力分支很多，只适合小数据。

接下来考虑怎样化简。

如果把木棍按：

  • 长度降序
  • 长度相同再按宽度降序

排序，那么从前往后看时，长度条件已经天然满足“不增”。

这时，一条合法加工链只剩下一个条件：

  • 宽度也要不增

于是问题转成：

  • 把排序后的宽度序列划分成最少条不升子序列

根据序列上的经典结论，这个最小划分数等于该序列的最长严格上升子序列长度。

所以最后只需要在宽度上做 LIS。

样例排序后

样例木棍排序后为：

编号 长度 宽度
1 5 2
2 4 9
3 3 5
4 2 1
5 1 4

对应宽度序列是：

2, 9, 5, 1, 4

其中一个最长严格上升子序列是：

2, 5

或

1, 4

长度都是 2，所以答案就是 2。
这也对应题面给出的最优安排：所有木棍至少要分成两条加工链。

DP 公式

排序后，只需要在宽度序列 w1,w2,…,wnw_1,w_2,\ldots,w_n 上求最长严格上升子序列。设 dpidp_i 表示以第 ii 根木棍结尾的最长严格上升子序列长度，则：

dpi=1+max⁡j<i, wj<widpj dp_i=1+\max_{j<i,\ w_j<w_i} dp_j

若不存在合法的 jj，则 dpi=1dp_i=1。最终答案为：

max⁡1⩽i⩽ndpi \max_{1\leqslant i\leqslant n} dp_i

公式解释：排序后长度维度已经保证不会破坏加工链条件，只剩宽度需要分析。最少的不升链覆盖数等于最长严格上升子序列长度，所以在宽度序列上做 LIS 即可。

代码

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

const int MAXN = 5005;

struct Stick {
    int l, w;
};

int n;
Stick a[MAXN];
int dp[MAXN]; // dp[i]：以第 i 根木棍结尾的最长严格上升子序列长度

bool cmp_stick(const Stick &x, const Stick &y) {
    if (x.l != y.l) {
        return x.l > y.l;
    }
    return x.w > y.w;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].w;
    }

    sort(a + 1, a + n + 1, cmp_stick);

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            // 长度已经按降序排好，只需要再要求宽度也严格上升。
            if (a[j].w < a[i].w) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

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

复杂度

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(n)O(n)

总结

这题的关键不是直接排加工顺序，而是先把二维条件变成一维序列问题。

排序解决长度约束，LIS 解决“最少不升链覆盖”问题，整个模型就清楚了。

一图流解析

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

一图流解析