956. 最高的广告牌

发表于 分类于 阅读次数： Waline： 本文字数： 667 阅读时长 ≈ 2 分钟

考点

  • 01背包
  • 差值DP
  • 滚动数组

思路

正常来说，会考虑f[i][j][k]，即考虑前i个棒子，第一堆的和为j，第二堆的和为k，但发现这样和暴力搜索并没有任何区别

然后发现规律，我只需要管两堆的差值即可，即差值DP

得到转移方程，这题我用Push方向，比较好写：

1
2
3
4
5
6
7
8
9
10
11
12
13
f[i][j]：在前i个棒子组成两堆差值为j的状态下，保存最大堆的值
现在已知f[i][j], 考虑对f[i+1]的转移
设x = rods[i+1]
不取rods[i+1], 则f[i+1][j] = max(f[i+1][j], f[i][j])

取rods[i+1]，把它放到当前两堆里的更大堆，差值变大，最大堆的值也更大了：
则f[i+1][j+x] = max(f[i+1][j+x], f[i][j] + x)

取rods[i+1]，把它放到当前两堆里的更小堆，且x <= j，那么差值减小，最大堆的值不变：
则f[i+1][j-x] = max(f[i+1][j-x], f[i][j])

取rods[i+1]，把它放到当前两堆里的更小堆，且x > j，修改差值，最大堆的值变大：
则f[i+1][x-j] = max(f[i+1][x-j], f[i][j] + x - j)

就得到了第一版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  static const int maxn = 25, maxm = 5e3 + 50;
  int n, m, f[maxn][maxm];
  int tallestBillboard(vector<int>& rods) {
    n = rods.size(), m = 0;
    for (int i = 0; i < n; ++i) m += rods[i];
    memset(f, 0xcf, sizeof(f));
    f[0][0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= m; ++j) {
        int x = rods[i];
        // 不选
        f[i + 1][j] = max(f[i + 1][j], f[i][j]);
        // 选，但是放高的
        if (j + x <= m) f[i + 1][j + x] = max(f[i + 1][j + x], f[i][j] + x);
        if (x <= j)
          // 选，放低的，j >= r
          f[i + 1][j - x] = max(f[i + 1][j - x], f[i][j]);
        else
          // 选，放低的，j < r
          f[i + 1][x - j] = max(f[i + 1][x - j], f[i][j] + x - j);
      }
    }
    return f[n][0];
  }
};

这里可以使用滚动数组进行优化，但是要注意，不可以滚成一维，因为每次同时要对j + r和j - r两个方向进行修改

得到第二版AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  static const int maxn = 25, maxm = 5e3 + 50;
  int n, m, f[2][maxm];
  int tallestBillboard(vector<int>& rods) {
    n = rods.size(), m = 0;
    for (int i = 0; i < n; ++i) m += rods[i];
    memset(f, 0xcf, sizeof(f));
    f[0][0] = 0;
    for (int i = 0; i < n; ++i) {
      memcpy(f[i + 1 & 1], f[i & 1], sizeof(f[i & 1]));
      for (int j = m; j >= 0; --j) {
        if (f[i & 1][j] == 0xcfcfcfcf) continue;
        int x = rods[i], y = abs(j - x), z = (x <= j ? 0 : x - j);
        if (j + x <= m)
          f[i + 1 & 1][j + x] = max(f[i + 1 & 1][j + x], f[i & 1][j] + x);
        f[i + 1 & 1][y] = max(f[i + 1 & 1][y], f[i & 1][j] + z);
      }
    }
    return f[n & 1][0];
  }
};