首先是一个数据范围为2000的，这个可以用平方算法做。

要使它成为一个非降序列的合并次数最小，我们可以贪心地想到要使合并后的值尽量小，不然就会导致后面需要的合并次数增多。

我们用c[i]记录前缀和，f[i]表示以i结尾的这一段序列的最后一个元素的值，g[i]表示到i为止的合并次数，那么就可以得到一个转移方程。

f[i]=c[i]-c[j](f[j]<=c[i]-c[j])

g[i]=g[j]+i-j-1;

因为c[i]-c[j]在downto的过程中是单调递增的，所以只要找到一个可以转移的就可以break了。

program Neayo;const        inf='sequence.in';        ouf='sequence.out';var        i,j,k,m,n,ans:longint;        g,f,c:array[0..1502]of longint;procedure init;var x:longint;begin     assign(input,inf);assign(output,ouf);     reset(input);rewrite(output);     readln(n);     for i:=1 to n do     begin          read(x);          c[i]:=c[i-1]+x;     end;     close(input);end;procedure go;begin     fillchar(f,sizeof(f),127);     f[0]:=0;g[0]:=0;     for i:=1 to n do      for j:=i-1 downto 0 do      if c[i]-c[j]>=f[j] then      begin           f[i]:=c[i]-c[j];           g[i]:=g[j]+i-j-1;           break;      end;    writeln(g[i]);end;begin     init;     go;     close(output);end.

到了1000000的数据范围，平方算法是绝对不可行的了。

但是转移方程还是正确的，由于它的单调性，于是我们加入单调队列将决策过程优化成O(nlogn)。

1 const 2         inf='ccl.in'; 3         ouf='ccl.out'; 4 var 5         i,j,k,n:longint; 6         ans:longint; 7         c:array[0..1000001]of int64; 8         g,f,q:array[0..1000001]of int64; 9 procedure init;10 begin11      assign(input,inf);assign(output,ouf);12      reset(input);rewrite(output);13      readln(n);14      for i:=1 to n do15      begin16           read(c[i]);17           c[i]:=c[i-1]+c[i];18      end;19      close(input);20 end;21 procedure go;22 var l,r:longint;23 begin24      fillchar(f,sizeof(f),127);25      l:=1;r:=1;f[0]:=0;q[1]:=0;26      for i:=1 to n do27      begin28           while (l
      
       =f[q[l+1]])do inc(l);29           f[i]:=c[i]-c[q[l]]+c[i];30           g[i]:=g[q[l]]+i-q[l]-1;31           while (r>l)and(f[i]<=f[q[r]])do dec(r);32           inc(r);33           q[r]:=i;34      end;35      writeln(g[n]);36 end;37 begin38      init;39      go;40      close(output);41 end.