P6771 [USACO05MAR] Space Elevator 太空电梯

题目描述

奶牛们要去太空了！它们打算用方块建造一座太空电梯。现在它们有 $N$ 种方块，第 $i$ 种方块有一个特定的高度 $h_i$，一定的数量 $c_i$。为了防止宇宙射线破坏方块，第 $i$ 种方块的任何部分不能超过高度 $a_i$。
请用这些方块堆出最高的太空电梯。

输入格式

第一行，一个整数 $N$；
第二行到 $N+1$ 行，第 $i+1$ 行三个整数 $h_i,a_i,c_i$，数字之间用空格分隔。

输出格式

共一行，一个整数，为太空电梯的高度。

输入 #1

3
7 40 3
5 23 8
2 52 6

输出 #1

48

说明/提示

对于 $100\mathrm{\%}$ 的数据：$1\le N\le 400$，$1\le h_i\le 100$，$1\le c_i\le 10$，$1\le a_i\le 4\times {10}^4$。

思路

先分析这个题目：每个方块有最大高度限制，那么到达某个累计高度，并且没有方块可以再往上放的时候就是最大的高度了 从动态规划的角度考虑这个题目，可以分解为子问题: 在$h_{max}$限制下，$h$能达到的最大值， 而： $dp[i][h_{\text{max}}]=max(dp[i-1][h_{\text{max}}],dp[i-1][h_{\text{max}}-h[i]])$

因此本题可以作为多重背包来解决

简单编写好二进制优化的多重背包后运行发现结果不对，

    for (int i = 1; i <= N; i++)
    {

        int s = items[i].c;
        // 二进制优化
        for (int c = 1; s >= c; s -= c, c <<= 1)
        {
            for (int j = 0; j <= h_max; j++)
            {
                int now_h = items[i].h * c;
                dp[i][j] = dp[i - 1][j];
                //  max(dp[i - 1][j], dp[i - 1][j - now_h] + now_h);
                if (j >= now_h && dp[i - 1][j] < dp[i - 1][j - now_h] + now_h && dp[i - 1][j - now_h] + now_h <= items[i].a)
                {
                    dp[i][j] = dp[i - 1][j - now_h] + now_h;
                }
            }
        }
        // 分割后的剩余
        if (s != 0)
        {
            for (int j = 0; j <= h_max; j++)
            {
                int now_h = items[i].h * s;
                dp[i][j] = dp[i - 1][j];
                //  max(dp[i - 1][j], dp[i - 1][j - now_h] + now_h);
                if (j >= now_h && dp[i - 1][j] < dp[i - 1][j - now_h] + now_h && dp[i - 1][j - now_h] + now_h <= items[i].a)
                {
                    dp[i][j] = dp[i - 1][j - now_h] + now_h;
                }
            }
        }
    }

运行结果：

3
7 40 3
5 23 8
2 52 6
25

经过分析，这题跟一般的背包问题有个明显区别是，这道题目中放置方块是有先后顺序的,如果先放了限高比较大的，再就放不了小的，但是反过来可以(这里有点类似于操作系统的作业调度，截止时间不同)，尝试一下先按照限高排序再进行dp

调整代码后并没有改变输出，debug的时候发现是dp[i][j] = dp[i - 1][j - now_h] + now_h;这里导致的，二进制拆分的时候不能用i-1, 这样物品就无法累加

然后做了一个小测试，发现了更大的bug

1
4 30 6
i: 1 c: 1 s: 6 dp[now][h_max]: 28 
i: 1 c: 2 s: 5 dp[now][h_max]: 28
i: 1 s: 3 dp[now][h_max]: 28
28

并没有被方块数量限制住，需要修复一下，原因是重复利用了，需要像01背包那样倒着遍历j,改为for (int j = h_max; j >= 0; j--)

现在成功得到了正确结果，提交一下试试。。。。一片WA

最后检查发现是由于排序的时候没把最后一个排上

sort(items + 1, items + N, [](const item &a, const item &b)
         { return a.a < b.a; });

修改成items + 1, items + N + 1就可以了（感谢deepseek）

题解

AC代码：

#include <bits/stdc++.h>
#define ll long long
#define debug(x) #x << ": " << x << " "
// #define debug(x) ""

using namespace std;

struct item
{
    int h;
    int a;
    int c;
};

item items[500];
int dp[500][40960];

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

    memset(dp, 0, sizeof(int) * 500 * 40960);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> items[i].h >> items[i].a >> items[i].c;
    }

    sort(items + 1, items + N + 1, [](const item &a, const item &b)
         { return a.a < b.a; });
    int h_max = items[N].a;
    int now = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int k = 1; k <= items[i].c; k++)
        {
            for (int j = items[i].a; j >= items[i].h; j--)
            {
                dp[now][j] = max(dp[now][j], dp[now][j - items[i].h] + items[i].h);
            }
        }
    }
    
    int m = 0;
    for (int i = 0; i <= h_max; i++)
    {
        // cout << debug(dp[now][i]);
        if (dp[now][i] > m)
        {
            m = dp[now][i];
        }
    }
    // cout << dp[now][h_max];
    cout << m;

    return 0;
}