跳转至

DS-10 动态规划-蛋糕塔

题目描述

有 \(n\) 种蛋糕，第 \(i\) 种蛋糕的高度为 \(h_i\)，价值为 \(v_i\)，每种蛋糕有无穷多块。

您需要选择若干块蛋糕，从下往上建成一个蛋糕塔。一块高度 \(\geq K\) 的蛋糕被称为“大蛋糕”。大蛋糕下方的所有蛋糕（不包括自己），高度会变为原来的 \(\frac{4}{5}\)。要求建成的蛋糕塔的高度不超过 \(T\)。

注意：蛋糕不会被重复压缩，您可以认为，如果一个蛋糕上面有大蛋糕，那它的高度就是原来的 \(\frac{4}{5}\)，否则就是原高度。

求建成一个蛋糕塔，使得蛋糕的价值之和最大。

样例1

C++
1
2
3
4
const int n = 3, T = 53, K = 25;
vector<int> h = {25, 5, 10};
vector<int> v = {100, 20, 40};
int bestAns = 240;
**样例一最优方案：**最上面放一块高度 \(25\) 的蛋糕，下面再放高度为 \(25\) 和 \(10\) 的，因为最上面 \(25\) 的是大蛋糕，因此下面全部蛋糕的高度都乘上 \(\frac{4}{5}\)，总高度 \(= 25 + 20 + 8 = 53\)，总价值 \(= 100 + 100 + 40\)

解题思路

记 f[j] 表示总高度为 j 时的最大价值，我们发现最好的情况只有两种

  1. 有大蛋糕 且 最上面的是大蛋糕
  2. 没有大蛋糕

如果有大蛋糕且最上面不是大蛋糕，则将大蛋糕拿出来放到最上面，价值不变的情况下高度减小，不劣

因此我们可以分两种情况讨论： 1. f1[j] 表示总高度为 j 时不考虑大蛋糕的压缩的最大价值 2. f2[j] 表示总高度为 j 时最上面是大蛋糕且考虑压缩的最大价值

对于 f1[j]，每个蛋糕都有无限个，即完全背包问题，状态转移方程为： $$ f1(j) = \max{f1(j), f1(j - h_i) + v_i} $$

对于 f2[j]，最上面是大蛋糕，下面的蛋糕都被压缩了，因此状态转移方程为： $$ f2(j) = \max{f2(j), f1((j - h_i) \times \frac{5}{4}) + v_i} $$

因为蛋糕无法被重复压缩，因此 f2 的状态转移方程中使用的是 f1。

最终答案为 \(\max\{f1[j], f2[j]\}\)，其中 \(0 \leq j \leq T\)

代码实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
int cakeTower(int n, int T, int K, 
              const vector<int> &h, 
              const vector<int> &v) {
    int f1[2005] = {0}, f2[1005] = {0}, ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = h[i]; j <= 2 * T; ++j) { // 可能放大蛋糕前会溢出一点高度
            f1[j] = max(f1[j], f1[j - h[i]] + v[i]);
        }
    }
    for (int j = 0; j <= T; ++j) ans = max(ans, f1[j]);

    for (int j = K; j <= T; ++j) {
        for(int i = 0; i < n; ++i) {
            if (h[i] < K) continue;
            if ((j - h[i]) % 4 != 0) continue;
            f2[j] = max(f2[j], f1[(j - h[i]) * 5 / 4] + v[i]);
        }
    }
    for (int j = K; j <= T; ++j) ans = max(ans, f2[j]);
    return ans;
}

评论