APIO2014 序列分割

未分类

可以发现切割顺序对答案没啥影响，那么默认从左到右切，就是很板子的斜率优化了。

#include <iostream>
#include <cstdio>
typedef long long LL;
#define int LL
const int MAXN = 2e5;
const int MAXK = 3e2;
int n, k;
int q[MAXN | 1], fa[MAXK | 1][MAXN | 1];
LL a[MAXN | 1], dp[MAXK | 1][MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline double slope(int i, int x, int y) {
  if (a[x] == a[y]) return -1e18;
  return 1.0 * (dp[i][y] - a[y] * a[y] - (dp[i][x] - a[x] * a[x])) / (-a[y] + a[x]);
}
void out(int i, int j) {
  if (i == 0) return;
  out(i - 1, fa[i][j]);
  printf("%d ", fa[i][j]);
}
signed main() {
  n = read();
  k = read();
  for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + read();
  for (int i = 1; i <= k; ++i) {
    int l = 1, r = 0;
    for (int j = 1; j <= n; ++j) {
      while (l < r && slope(i - 1, q[l], q[l + 1]) <= a[j]) ++l;
      dp[i][j] = dp[i - 1][q[l]] + (a[j] - a[q[l]]) * a[q[l]];
      fa[i][j] = q[l];
      while (l < r && slope(i - 1, q[r - 1], q[r]) >= slope(i - 1, q[r], j)) --r;
      q[++r] = j;
    }
  }
  printf("%lld\n", dp[k][n]);
  out(k, n);
  return 0;
}