[USACO12MAR] Cows in a Skyscraper G

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

设 dp[mask] 为安排完这些牛后的最优状态，状态记录最少电梯趟数以及该趟数下最后一趟电梯的最小已载重量。

OJ: luogu

题目 ID: P3052

难度:普及/提高-

标签:状态压缩动态规划位运算经典题

日期: 2026-06-21 05:13

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 N 头牛，每头牛有一个重量。

电梯每次有承重上限 W，要求把所有牛运下楼，问最少需要多少趟电梯。

思路

先看一个适合小数据验证的回溯暴力：

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

int n, limit_w;
int w[25];
int ride_weight[25];
int ans;

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

    for (int i = 1; i <= used; i++) {
        if (ride_weight[i] + w[idx] <= limit_w) {
            ride_weight[i] += w[idx];
            dfs(idx + 1, used);
            ride_weight[i] -= w[idx];
        }
    }

    ride_weight[used + 1] = w[idx];
    dfs(idx + 1, used + 1);
    ride_weight[used + 1] = 0;
}

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

    // brute.cpp：回溯把每头牛放入已有电梯或新开一趟电梯。
    cin >> n >> limit_w;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    sort(w + 1, w + n + 1, greater<int>());
    memset(ride_weight, 0, sizeof(ride_weight));
    ans = n;
    dfs(1, 0);
    cout << ans << '\n';
    return 0;
}

回溯的思路是：当前这头牛可以放进已有某趟电梯，或者新开一趟电梯。 但这样会重复遇到很多“同一批牛已经安排完”的状态。

本题 N<=18，所以可以做状压 DP。

设 dp[mask] = (rides, weight)：

  • mask 表示已经安排好的牛集合
  • rides 表示已经用了多少趟电梯
  • weight 表示在这些最优方案中，最后一趟电梯当前装了多少重量

比较两个状态时：

  • 先让 rides 更小
  • 若 rides 相同，让 weight 更小

因为趟数相同的前提下，最后一趟越轻，后面就越容易继续塞牛。

转移时加入一头还没安排的牛：

  • 如果最后一趟还能装下，就放进去
  • 否则新开一趟电梯

这就是经典的“最少电梯趟数”状压模型。

代码

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

const int MAXN = 18;

struct State {
    int rides;
    int weight;
};

int n, limit_w;
int w[MAXN + 1];
State dp[1 << MAXN];

bool better(const State &a, const State &b) {
    if (a.rides != b.rides) {
        return a.rides < b.rides;
    }
    return a.weight < b.weight;
}

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

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

    int full = 1 << n;
    for (int i = 0; i < full; i++) {
        dp[i] = {n + 1, 0};
    }
    dp[0] = {1, 0};

    for (int mask = 0; mask < full; mask++) {
        for (int i = 1; i <= n; i++) {
            if (mask & (1 << (i - 1))) {
                continue;
            }
            State nxt = dp[mask];
            if (nxt.weight + w[i] <= limit_w) {
                nxt.weight += w[i];
            } else {
                nxt.rides++;
                nxt.weight = w[i];
            }

            int to = mask | (1 << (i - 1));
            if (better(nxt, dp[to])) {
                dp[to] = nxt;
            }
        }
    }

    cout << dp[full - 1].rides << '\n';
    return 0;
}

复杂度

时间复杂度 O(N2N)O(N 2^N)，空间复杂度 O(2N)O(2^N)。

总结

这题最关键的不是只记录“最少趟数”，而是还要顺手维护“最后一趟当前重量”这个次关键量。 这类“字典序最优状态”在状压 DP 里很常见。