题解 P3648 【[APIO2014]序列分割】

学委 · 2019-01-27 13:34:11 · 题解

对于一类 DP 形如 f[i] = \min_{L_i \le j \le R_i}(f[j] + sum(i, j))，斜率优化可以维护 DP 中的最佳继承。

这题也许是一道很好的斜率优化入门题。

状态简化

切的顺序可以自定，似乎状态很复杂。

尽可能简化状态。看看有没有这样一个结论：切的位置可以完全决定获得的分数（即与顺序无关）。

怎么验证？从每个元素获得的系数来考虑（即“我到底与哪些数字相乘了”）。

假设打算这样分割（圆圈序号表示分割的位置）：

8 7　①　6 3 17　②　20 14 15　③　0 2 3

可以考虑数字 17 与谁相乘：

• 不管按什么顺序切割，与块内的元素从来不会相乘。

• 那么和右边那个 2 相乘过吗？在首次和 2 分离的时候（不管先切 ② 还是 ③）相乘了，此后两者无法再次“分离”，一定不会再次相乘。

  跟其它块外元素也一样，分离肯定要分，但只分离一次。

不管切的顺序如何，对于某个块内的单个元素，它：

• 与块内的元素肯定不会相乘；

• 与其它块内的任何一个元素肯定相乘恰好一次。

所以，切的位置决定获得的分数，什么顺序都一样。

下面都是状态都是假定从前往后分割，比较方便。

现在甚至可以用 dp[i][t] 表示在前 i 个数中切了 t 刀（为了方便继承，定最后一个切割位置为 i）能获得的最高分数。比较直观的继承方式是枚举上一个切割位置，然后切 i 获得此次分数。

for (int i = 1; i <= n; ++i)
  for (int t = 1; t <= k; ++t) {
    // 现在求 dp[i][t]

    for (int j = 1; j <= i - 1; ++j) // 选择哪个位置作为“上一个分割位置”？这是决策
      if (dp[j][t - 1] + // 该切割位置的已得分数
         (sum[i] - sum[j]) * (sum[n] - sum[i]);// 这是本次切割的分数，用前缀和很方便地表示出左右两块
  }

这样能求出答案，但是超时。我觉得继承大概要 O(1)，怎么维护最优决策？

斜率优化

现在眼前有两个选择：继承 j1 或继承 j2 (j1 < j2)。

如果 j1 优于 j2，即：

暂时省略 dp 数组的第二维

移项：

再移项，同时注意符号，sum[j2] - sum[j1] 肯定非负（可能为 0，需另加考虑）。

对于 i 来说，j1 和 j2 只要满足这个不等式就说明决策 j1 优于 j2。

现在施加可视化魔法。在坐标系上，以 sum[j] 为横坐标，dp[j] 为纵坐标，把每个决策表示为点。

这里有 4 个备选决策。注意，sum[] 和 dp[] 都是单调不减的。

现在不等式左边可以视为 j1、j2 连线的斜率；而 j1 优于 j2 的条件是斜率足够小（小于“i 的某个常数”）。

观察。j2 看起来像是“下沉点”，即它有一个糟糕的特征：斜率 k(j1, j2) < k(j2, j3)；如果 j2 优于 j3，那么由上面的条件可知，j1 一定优于 j2，所以它不可能成为最佳决策。 我们删掉下沉点 j2，留下的点之间，斜率单调递减。

• 现在备选决策之间，相邻点斜率单调递减。可能是 7　6　4　3.5　1　0.9。

• 再回顾一下“更优”的条件：斜率足够小。

二分查找到第一个小于 sum[n] - sum[i] 的斜率。由于决策之间的斜率是递减的，保证前面的决策都没它好，它比后面的决策都好。

可以用单调队列代替二分查找：

• 注意到 “i 的常数”（即 sum[n] - sum[i]） 是单调递减的。

• 计算 dp[i][t] 的步骤：对 “已切 t - 1 刀”备选决策队列进行筛选，从前往后删掉斜率太大的，直到队首斜率小于 sum[n] - sum[i]，队首就是对于 i 最优的。

  因为随着 i 的上升，筛选只会越来越严格，所以不必管之前就被筛掉的决策，于是单调队列可以维护。

• 算出 dp[i][t] 后，更新 t 的决策队列，从后往前删掉下沉点，再加入 dp[i][t]。

注意：

• 对于第二维的每个 t（已切的刀数）维护一个单调队列。

• 继承了 t - 1 的最优策略以后，更新 t 的备选决策。

• 序列元素只是非负，因此可能会有横坐标相同的点。处理方法可见代码。

• 可以直接记录决策。

• 最后寻找答案，需要看看最后一刀切在哪里是最优的。

#include <cstdio>
#include <cctype>
typedef long long LL;

const int N = 100010;

int n, k, q[N][210], l[210], r[210], d[210], pre[N][210];
LL a[N], sum[N], dp[N][210];
inline double K(int t, int j1, int j2) {
  if (sum[j1] == sum[j2])
    return 1e18;// 赋极大值，入队时会把横坐标相同的点排挤掉 
  return (double)(dp[j2][t] - dp[j1][t]) /
    (sum[j2] - sum[j1]);
}

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i)
    scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];

  for (int t = 0; t <= k; ++t)
    q[l[t] = r[t] = 1][t] = 0; // 该层的单调队列 

  for (int i = 1; i <= n; ++i) {
    double k_top = sum[n] - sum[i]; // 考官的要求

    for (int t = k; t >= 1; --t) { // 倒序枚举楼层，防止自己“选择自己作为上一个分割点”。其实正序也不会错，因为该选择太差

      while (l[t - 1] <= r[t - 1] - 1) {
        int j1 = q[l[t - 1]][t - 1], j2 = q[l[t - 1] + 1][t - 1];
        double k = K(t - 1, j1, j2);
        if (k > k_top)
          ++l[t - 1];
        else
          break;
      }

      int v = q[l[t - 1]][t - 1];// 决策 
      dp[i][t] = dp[v][t - 1] +
        (sum[n] - sum[i]) * (sum[i] - sum[v]);

      pre[i][t] = v;

      // 添加新的决策（入队），注意第二维不同了 
      while (r[t] >= l[t] + 1) {
        double k2 = K(t, q[r[t]][t], i),
          k1 = K(t, q[r[t] - 1][t], q[r[t]][t]);
        if (k1 < k2)
          --r[t];
        else
          break;
      }
      q[++r[t]][t] = i;
    }
  }

  {
    int t = k, i = 0; LL ans = 0;
    for (int j = 1; j <= n; ++j) // 枚举最后一刀
      if (dp[j][k] > ans)
        ans = dp[j][k], i = j;

    printf("%lld\n", ans);

    while (t) {
      d[t] = i;
      i = pre[i][t--];
    }

    for (int j = 1; j <= k; ++j)
      printf("%d", d[j]), putchar((j == k) ? ('\n') : (' '));
  }
  return 0;
}