blob.jpg

int a[3005], n, m, pre[3005], q[3005], p;
ll f[2][3005];
inline lf slope(int x, int y) {
  return (f[!p][x] - f[!p][y] + sqr(pre[x]) - sqr(pre[y])) / (1.0 * pre[x] - pre[y]);
}
int main() {
#ifdef LOCAL_DEBUG
  Debug = 1; double tim1 = clock();
  // freopen("data.in", "r", stdin) && freopen("data.out", "w", stdout);
#endif 
  in, n, m;
  lop(i,1,n) {in, a[i]; pre[i] = pre[i-1] + a[i];}
  lop(i,1,n) f[0][i] = infl;
  lop(i,1,m) {
    p = i & 1;
    int h = 0, t = 0;
    lop(j,1,n) {
      while(h < t && slope(q[h+1], q[h]) < 2 * pre[j]) ++h;
      f[p][j] = f[!p][q[h]] + sqr(pre[j] - pre[q[h]]);
//      cout << p << ' ' << j << ' ' << f[p][j] << endl;
      while(h < t && slope(q[t], q[t-1]) > slope(q[t], j)) --t;
      q[++t] = j;
    }
  }
  out, f[p][n] * m - sqr(pre[n]);
#ifdef LOCAL_DEBUG
  fprintf(stderr, "\ntime:%.5lfms", (clock() - tim1) / CLOCKS_PER_SEC * 1000);
#endif
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注