POJ3709

博客终于有一篇OI向的文章啦!

POJ3709

题面

  给定一个长度为$n$一个序列,你可以使序列中的某一个项减小$1$。问要使序列中的每一项都满足其他项中至少要有$k-1$项和它相同,最少进行多少次操作。

题解

暴力

  首先,我们很容易发现对于$a_i$,我们只可能从$i$后找出至少$k-1$个数,并将它们减小至$a_i$。所以我们可以定义$dp_i$表示前$i$个元素已经处理完最少需要的操作次数。显然有

    $dp_i = min\{dp_{j - 1} + (a_i - a_j) + (a_{i - 1}- a_j) + (a_{i - 2} - a_j) + … + (a_{i - j + 1} - a_j)\}$

  这个式子显然可以用前缀和优化,用$s_i$表示$a_1$到$a_i$的和。然后式子会变成这样:

    $dp_i = min\{dp_{j - 1} + s_i - s_j - a_j × (i - j)\}$

  核心的转移代码长这样:

for (int i = k; i <= n; ++i) {
  for (int j = 1; j <= i - k + 1; ++j) {
    LL cost = s[i] - s[j] - a[j] * (i - j);
    dp[i] = min(dp[i], dp[j - 1] + cost);
  }
}

斜率优化

  然后我们考虑怎么优化。难点在于$a_j × (i - j)$这个东西很难搞,不能用单调队列优化。通常对于这种转移中有和$j$有关的乘积形式的式子,我们用斜率优化来加速$DP$

  我们假设$dp_j$比$dp_k$优,那么有如下式子:

    $dp_{j - 1} - s_j + a_j × j - a_j × i < dp_{k - 1} - s_k + a_k × k - a_k × i$

  化简可得:

    $\frac{dp_{j - 1} - s_j + a_j × j - dp_{k - 1} + s_k - a_k × k}{a_j - a_k} < i$

  于是我们就有了一个评估一个状态优劣的方法。当有两个状态$dp_j$和$dp_k$。如果上面的式子小于$i$,那么说明$j$比$k$优。我们可以发现上面的式子长得很像$\frac{\Delta y}{\Delta x}$,也就是斜率$k$,所以我们将这种评价两个状态的方法称为斜率优化。

  如图:

ZUfb1s.jpg

  此时$j$显然不是最优。

ZUfHpj.jpg

  此时$j$最优。

  因为$i$肯定递增,所以我们只要维护其中一个凸壳。根据上面的图,我们知道要维护的是下凸壳。然后这道题还有一个坑点上面式子中的分母$a_j-a_k$可能为$0$,所以我们判断斜率必须用乘积的形式。

代码

// Author: 23forever
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long LL;
const int MAXN = 500000;
using namespace std;

inline int read() {
  int x = 0, w = 1;
  char c = ' ';

  while (!isdigit(c)) {
    c = getchar();
    if (c == '-') w = -1;
  }

  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }

  return x * w;
}

int n, k, que[MAXN + 5], f, r;
LL a[MAXN + 5], s[MAXN + 5], dp[MAXN + 5];

LL fy(int x, int y) {
  int val = dp[x - 1] - s[x] + a[x] * x - dp[y - 1] + s[y] - a[y] * y;
  return val * 1.0;
}

LL fx(int x, int y) {
  return a[x] - a[y];
}

void init() {
  n = read(), k = read(); 
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    s[i] = s[i - 1] + a[i];
  }

  f = 1, r = 0;
}

int main() {
#ifdef forever23
  freopen("test.in", "r", stdin);
  //freopen("test.out", "w", stdout);
#endif

  int t = read();
  while (t--) {
    init();

    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    que[++r] = 1;

    for (int i = k; i <= n; ++i) {
      while (f < r && fy(que[f], que[f + 1]) >= i * fx(que[f], que[f + 1])) ++f;
      int j = que[f], cost = s[i] - s[j] - a[j] * (i - j);
      dp[i] = dp[j - 1] + cost;

      int p = i - k + 2;
      if (p > k) {
        while (f < r && fy(que[r - 1], que[r]) * fx(que[r], p) >= fy(que[r], p) * fx(que[r - 1], que[r])) --r;
        que[++r] = p;
      }
    }

    printf("%lld\n", dp[n]);
  }
}

本博客所有文章均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处
本文链接:https://23forever.com/2019/07/02/POJ3709/