1 条题解
-
0
[X] Tower(dp_x)题解
题意简述
块积木,第 块重量 、坚固度 、价值 。挑若干块堆成塔,要求塔中每块积木上方的总重不超过其 。求价值之和最大。
思路
第一步:确定最优堆叠顺序
结论:把积木按 升序从下往上堆(或等价地:排序后按顺序做 0/1 背包)。
证明(交换论证):设两块积木 相邻, 在上、 在下,需要
若 ,则把 放到 上面也是合法的(可验证约束不会变紧)。因此总存在一个"按 升序自下而上"的最优方案。
第二步:DP
按 排好序后,从前到后(自下而上)决定放不放:
设 = 已选积木的总重为 时的最大价值。
放第 块时,它将被放在已有塔的下面,所以要求"上方总重" :
$$f_{j + w_i} = \max\left( f_{j+w_i},\; f_j + v_i \right) \quad (j \le s_i).$$注意 从大到小枚举(0/1 背包)。
第三步:重量的上界
塔的总重不会超过"最底下一块"的 ,因为最底下的那块承受着上方全部重量。所以 ,DP 的重量维度只需开到 。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct Blk { int w, s; long long v; }; int main() { int n; scanf("%d", &n); vector<Blk> b(n); for (int i = 0; i < n; i++) scanf("%d %d %lld", &b[i].w, &b[i].s, &b[i].v); sort(b.begin(), b.end(), [](const Blk& x, const Blk& y) { return x.w + x.s < y.w + y.s; }); const int MAXD = 20005; static long long f[20005]; for (int d = 0; d < MAXD; d++) f[d] = -(1LL << 60); f[0] = 0; for (int i = 0; i < n; i++) { int w = b[i].w, s = b[i].s; long long v = b[i].v; for (int j = min(s, MAXD - 1 - w); j >= 0; j--) if (f[j] > -(1LL << 59)) f[j + w] = max(f[j + w], f[j] + v); } long long ans = 0; for (int d = 0; d < MAXD; d++) ans = max(ans, f[d]); return printf("%lld\n", ans), 0; }易错点
- 排序依据必须是 ,不是 、不是 、也不是 。
- 转移的条件是 (上方重量不超过坚固度),不是 。
- 重量维度开到 即可,开到 ()会 TLE/MLE。
- 价值之和可达 ,必须
long long(样例 3 是 )。 - 全正,答案至少为 ,所以 的初值用极小数即可(不会选出空塔之外的坏值)。
数据说明
共 16 组:4 组官方样例;、两块相同、三块全同、单块 的边界; 随机; 随机、全 、全 、 小 大的构造组。
- 1
信息
- ID
- 33
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者