[bzoj4518][Sdoi2016]征途-斜率优化

Brief Description

Pine开始了从S地到T地的征途。

从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。

Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。

Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

帮助Pine求出最小方差是多少。

设方差是v，可以证明，v×m2。

Algorithm Design

不难设计出DP方程,

\[f(i, j) = f(i-1, k) + w(j,k)
\]

\[w(j, k)=f(i-1,k)+(s[k]-s[j])^2
\]

很容易得到斜率优化的式子:

\[\frac{f(i-1,j)-f(i-1,k)+s_j^2-s_k^2}{2(s_j-s_k)}\leqslant s_i
\]

然后乱搞就好辣

Notice

注意特判分母为0

QAQ

另外吐嘈一下,这个题写\(O(n^3)\)的暴力居然有60分!!!

Code

#include <algorithm>

#include <cctype>

#include <cstdio>

#define ll long long

const ll inf = 99999999999;

const int maxn = 60010;

// const int maxm = 30010;

ll f[2][maxn];

int n, m, now = 1;

ll s[maxn];

ll sq(ll x) { return x * x; };

ll read() {

  int x = 0, f = 1;

  char ch = getchar();

  while (!isdigit(ch)) {

    if (ch == '-')

      f = -1;

    ch = getchar();

  }

  while (isdigit(ch)) {

    x = x * 10 + ch - '0';

    ch = getchar();

  }

  return x * f;

}

inline double calck(int i, int j) {

  if (s[j] - s[i] == 0)

    return inf;

  return (f[now ^ 1][j] - f[now ^ 1][i] + sq(s[j]) - sq(s[i])) /

         ((s[j] - s[i]) * 2);

}

int que[maxn], head, size, tail;

int main() {

  /*  freopen("menci_journey.in", "r", stdin);

    freopen("menci_journey.out", "w", stdout); */

  n = read();

  m = read();

  for (int i = 1; i <= n; i++)

    s[i] = read();

  for (int i = 1; i <= n; i++)

    s[i] += s[i - 1];

  for (int i = 1; i <= n; i++)

    f[0][i] = inf;

  for (int i = 1; i <= m; i++) {

    head = tail = 0;

    size = 1;

    for (int j = 1; j <= n; j++) {

      while (size >= 2) {

        int a = que[head];

        int b = que[head + 1];

        if (calck(a, b) < s[j]) {

          head++;

          size--;

          if (size < 2)

            break;

        } else

          break;

      }

      int k = que[head];

      f[now][j] = f[now ^ 1][k] + sq(s[j] - s[k]);

      if (size >= 2) {

        int x = que[tail];

        int y = que[tail - 1];

        while (calck(y, x) > calck(x, j)) {

          tail--;

          size--;

          if (size < 2)

            break;

          x = que[tail];

          y = que[tail - 1];

        }

      }

      que[++tail] = j;

      size++;

    }

    now ^= 1;

  }

  // printf("%lld\n", f[now ^ 1][n]);

  ll ans = m * f[now ^ 1][n] - s[n] * s[n];

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

}