1335. 工作计划的最低难度

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

考点

  • 划分DP
  • 单调栈

思路

划分DP

裸的划分DP，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  static const int inf = 0x7f7f7f7f;
  int minDifficulty(vector<int>& jobDifficulty, int d) {
    int f[305][305];
    memset(f, 0x7f, sizeof(f));
    f[0][0] = 0;
    int n = jobDifficulty.size();
    for (int j = 1; j <= d; ++j) {
      for (int r = j; r <= n; ++r) {
        int mx = -1;
        for (int l = r; l >= j; --l) {
          mx = max(mx, jobDifficulty[l - 1]);
          if (f[j - 1][l - 1] != inf)
            f[j][r] = min(f[j][r], f[j - 1][l - 1] + mx);
        }
      }
    }
    return f[d][n] == inf ? -1 : f[d][n];
  }
};

注意，如果压缩为一维，要注意n < d时的不可能情况，否则数组保留的可能还是上次的可行性解：

看一个具体反例：

  • jobDifficulty = [9]
  • d = 2

显然无法在 2 天内安排 1 个任务且每天至少一个任务，所以答案应该是 -1。

如果不特判的话，执行过程：

  1. 初始化：f[0] = 0, f[1..n] = inf
  2. 第一天 j = 1：
    • r = 1：
      • mx = 9
      • 用 f[0] 更新 f[1] = 9
    • 结束后，此时数组含义是：f[1] = f[1][1] = 9
  3. 第二天 j = 2：
    • for (int r = n; r >= j; --r) 里，n=1, j=2，循环根本不进
    • 所以 f[1] 仍然是第一次循环留下来的 9，即上一行的 f[1][1]，而不是 f[2][1]
  4. 最后直接返回 f[n] = 9

但是二维版里返回的是 f[d][n]，也就是 f[2][1]，这格从来没被更新过，仍然是 inf，所以返回 -1，是正确的。

所以在 n < d 的场景下，不特判的写法最后拿到的是「天数不够的状态」f[1][1]，而不是「真正要的」f[2][1]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  static const int inf = 0x7f7f7f7f;
  int minDifficulty(vector<int>& jobDifficulty, int d) {
    int n = jobDifficulty.size();
    // 滚动数组要注意加这一句
    if (n < d) return -1;
    int f[305];
    memset(f, 0x7f, sizeof(f));
    f[0] = 0;
    for (int j = 1; j <= d; ++j) {
      for (int r = n; r >= j; --r) {
        int mx = -1;
        f[r] = inf;
        for (int l = r; l >= j; --l) {
          mx = max(mx, jobDifficulty[l - 1]);
          if (f[l - 1] != inf) f[r] = min(f[r], f[l - 1] + mx);
        }
      }
    }
    return f[n] == inf ? -1 : f[n];
  }
};

单调栈

先回忆一下单调栈的特性：

  • 单调队列每次都会有区间范围限制，而单调栈后续所有的情况都从同一起点出发，类似前缀和
  • 每次只用栈顶就可以获得答案，而不需要栈内其他元素

对固定的 day，计算一整行 \(f[\text{day}][i]\) 时，我们按 i 从左到右递增地扫描。

对于固定右端 i，所有可能的左端 k 满足： \[ k \in [\text{day}..i] \] 每个 k 对应最后一天做区间 \[ [k..i] \] 而这些区间的最大值 \[ \max(a[k..i]) \] 随着 k 从右向左移动是 单调不减 的，即所有候选 k 会自然分成如下几段（块）：

  • 块 1：所有 k 使得 \(\max(a[k..i]) = M_1\)
  • 块 2：所有 k 使得 \(\max(a[k..i]) = M_2\)
  • 块 3：所有 k 使得 \(\max(a[k..i]) = M_3\)
  • ……

其中 \[ M_1 < M_2 < M_3 < \dots \] 也就是说： 随着区间左端向左扩展，最大值只会在若干个“跳点”上升。

这些“跳点”恰好就是区间最大值发生更新的位置，它们的右端点代表就是： \[ pos_1,\ pos_2,\ pos_3 \dots \] 于是我们可以为每一块定义一个代表元素：

  • pos：该块的“右端点代表”（也是该块最大值的来源）
  • val：该块内部所有 k 的

\[ \min f[\text{day}-1][k-1] \]

用一个单调栈维护所有块的 (pos, val)，并且保证： \[ a[pos_1] > a[pos_2] > a[pos_3] > \dots \] 即栈中 a[pos] 严格递减。

转移机制

当右端 i 向右推到一个新工作时，新难度为： \[ x = a[i] \] 我们要更新 \[ f[\text{day}][i] \] 此时有三类情况：

情况 1：只考虑最后一天只做 a[i]

这是区间 \([i..i]\)，最大值 = a[i] 前一部分由 \[ f[\text{day}-1][i-1] \] 提供。

令： \[ mi = f[\text{day}-1][i-1] \]

情况 2：合并所有最大值小于等于 x 的块

单调栈顶代表的块若满足 \[ a[pos] \le x \] 则说明：

  • 在该块中，所有区间最大值原本是 a[pos]
  • 但现在加上 a[i] 之后，新的最大值变成 x

因此，这些块会被完全合并到“最大值 = x”这个新块中。

对于这些块，

  • 它们内部的所有 k 都可以延伸到 i，并且

\[ \max(a[k..i]) = x \]

每个块都提供其代表 val = min f[day-1][k-1]。

于是我们更新： \[ mi = \min(mi,\ \text{block.val}) \] 并弹出这些块：

1
2
3
4
while (!st.empty() && a[st.top().pos] <= x) {
    mi = min(mi, st.top().val);
    st.pop();
}

合并完成后，mi 代表的是：

“所有最大值会被提升成 x 的候选 k 的 f[day-1][k-1] 的最小值”。

情况 3：栈中仍有块，其最大值 > x

如果栈不为空，说明还有块满足 \[ a[pos] > x \] 也就是说，对于这些块的 k： \[ \max(a[k..i]) = a[pos] \] 不会变成 x。

因此，这些 k 对应的最小代价已经在 \[ f[\text{day}][pos] \] 中计算好了。

所以我们有另一类候选： \[ f[\text{day}][pos] \] 最终对两类情况取最优：

  • “最大值变为 x” 的那部分： \[ mi + x \]

  • “最大值保持为 a[pos]” 的那部分： \[ f[\text{day}][pos] \]

于是更新：

1
2
3
4
if (!st.empty())
    f[day][i] = min(mi + x, f[day][st.top().first]);
else
    f[day][i] = mi + x;

情况 4：将当前 i 作为新块入栈

新的块：

  • 右端点代表是 i
  • 该块所有区间最大值 = x
  • 该块最小前缀代价为 mi

故入栈：

1
st.push({i, mi});

代码如下：

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
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int minDifficulty(vector<int>& jobDifficulty, int d) {
    int n = jobDifficulty.size();
    if (n < d) return -1;
    int f[15][305];
    memset(f, 0x3f, sizeof(f));

    // day = 1：前缀最大值
    int mx = -1;
    for (int i = 1; i <= n; ++i)
      mx = max(mx, jobDifficulty[i - 1]), f[1][i] = mx;

    for (int day = 2; day <= d; ++day) {
      stack<pair<int, int>> st; // {pos, bestPrev}
      for (int i = day; i <= n; ++i) {
        int x = jobDifficulty[i - 1];
        int mi = f[day - 1][i - 1]; // 只做 job i 的前缀代价

        // 合并所有 job[pos] <= x 的块
        while (!st.empty() && jobDifficulty[st.top().first - 1] <= x) {
          mi = min(mi, st.top().second);
          st.pop();
        }

        if (!st.empty())
          f[day][i] = min(mi + x, f[day][st.top().first]);
        else
          f[day][i] = mi + x;

        st.push({i, mi});
      }
    }
    return f[d][n];
  }
};