BZOJ 3675

PASCAL的常数啊QAQ

传送门

设最后分成的各个子序列的和分别为$S_1,S_2,\cdots,S_{k+1}$，那么答案就是
$$\sum_{i=1}^kS_i\sum_{j=i+1}^{k+1}S_j$$

与分割的顺序无关，然后可以搞出DP方程
$$F_{i,k}=max\lbrace F_{j,k-1},j\in[1,i)\rbrace+sum_j\times(sum_i-sum_j)$$

取$0<a,b<i$，决策$a$优于决策$b$当且仅当

$$F_{a,k}+sum_a\cdot sum_i-{sum_a}^2>F_{b,k}+sum_b\cdot sum_i-{sum_b}^2$$

$$\frac{(F_{a,k}-{sum_a}^2)-(F_{b,k}-{sum_b}^2)}{sum_a-sum_b}>-sum_i$$

然后就是斜率优化的事了…（只用滚动数组就够了）

C++平均10s PASCAL最快25s（我30s）是要闹哪样

program bzoj_3675;
const eps=1e-6;
var f,g:array[0..100000,0..1]of int64;
    sum,q:array[0..100000]of longint;
    n,m,hd,tl,i,j,t:longint;
begin
  readln(n,m);
  sum[0]:=0;
  for i:=1 to n do
  begin
    read(t);
    sum[i]:=sum[i-1]+t;
    g[i,0]:=-int64(sum[i])*int64(sum[i]);
  end;
  t:=0;
  for j:=1 to m do
  begin
    hd:=1;
    tl:=1;
    q[1]:=0;
    t:=t xor 1;
    for i:=1 to n do
    begin
      while (hd<tl)and(g[q[hd],t xor 1]-g[q[hd+1],t xor 1]<-int64(sum[i])*int64(sum[q[hd]]-sum[q[hd+1]])+eps) do inc(hd);
      f[i,t]:=f[q[hd],t xor 1]+int64(sum[q[hd]])*int64(sum[i]-sum[q[hd]]);
      g[i,t]:=f[i,t]-int64(sum[i])*int64(sum[i]);
      while (hd<tl)and((g[q[tl-1],t xor 1]-g[q[tl],t xor 1])*int64(sum[i]-sum[q[tl]])+eps>(g[q[tl],t xor 1]-g[i,t xor 1])*int64(sum[q[tl]]-sum[q[tl-1]])) do dec(tl);
      inc(tl);
      q[tl]:=i;
    end;
  end;
  writeln(f[n,t]);
end.