本地对拍了上万组数据没有一个错了,各种数据都差不多有
然后交就WA,求神牛解答.

如果有闲心可以检查一下蒟蒻的代码

Source Code

Problem: 3016			User: Hoblovski
Memory: N/A			Time: N/A
Language: Pascal		Result: Wrong Answer
Source Code

{$INLINE ON}
program poj3016;

type pnode=^tnode;
     tnode=record
        v,d:longint;
        l,r:pnode;
     end;

const maxn=1017;
      maxm=17;

var s,len,isum,osum,icnt,ocnt:array[0..maxn] of longint;
    cost:array[0..maxn,0..maxn] of longint;
    f:array[0..maxn,0..maxm] of longint;
    que:array[0..maxn*5] of pnode;
    node:array[0..maxn] of pnode;
    n,m,rer,rer0:longint;
    null:pnode;

function min(i,j:longint):longint; inline; begin
if i<j then exit(i) else exit(j);  end;

procedure leftheap_init(n:longint);
var i:longint;
begin
new(null); with null^ do begin
        v:=0; d:=-1; l:=null; r:=null;
end; filldword(node,(n+1),longint(null));
end;

function merge(var i,j:pnode):pnode; inline;
begin
if i=null then exit(j);
if j=null then exit(i);
if j^.v>i^.v then begin
        merge:=i; i:=j; j:=merge;
end;
i^.r:=merge(i^.r,j);
if i^.l^.d<i^.r^.d then begin
        merge:=i^.l; i^.l:=i^.r; i^.r:=merge;
end; i^.d:=i^.r^.d+1; exit(i);
end;

function exmax(var i:pnode):pnode; inline;
begin
exmax:=i; i:=merge(i^.l,i^.r);
end;

procedure getcost(st:longint);
var i,j:longint;
    k:int64;
begin
rer:=0; k:=0; rer0:=0;
fillchar(isum,sizeof(isum),0); fillchar(osum,sizeof(osum),0);
fillchar(icnt,sizeof(icnt),0); fillchar(ocnt,sizeof(ocnt),0);
fillchar(len,sizeof(len),0);
for i:=st to n do begin
        inc(rer); new(node[rer]); inc(rer0); que[rer0]:=node[rer];
        with node[rer]^ do begin
                v:=s[i]; d:=0; l:=null; r:=null;
        end; len[rer]:=1;
        icnt[rer]:=1;           ocnt[rer]:=0;
        isum[rer]:=s[i];        osum[i]:=0;
        while (rer>1)and(node[rer-1]^.v>=node[rer]^.v) do begin
                dec(k,icnt[rer]*node[rer]^.v    -isum[rer]  +osum[rer]  -ocnt[rer]*node[rer]^.v);
                dec(k,icnt[rer-1]*node[rer-1]^.v-isum[rer-1]+osum[rer-1]-ocnt[rer-1]*node[rer-1]^.v);
                dec(rer); inc(len[rer],len[rer+1]); node[rer]:=merge(node[rer],node[rer+1]);
                inc(icnt[rer],icnt[rer+1]);      inc(ocnt[rer],ocnt[rer+1]);
                inc(isum[rer],isum[rer+1]);      inc(osum[rer],osum[rer+1]);
                isum[rer+1]:=0; osum[rer+1]:=0; node[rer+1]:=null; icnt[rer+1]:=0; ocnt[rer+1]:=0; len[rer+1]:=0;
                while (icnt[rer]>((len[rer]+1)>>1)) do begin
                        j:=exmax(node[rer])^.v;
                        dec(icnt[rer]);         inc(ocnt[rer]);
                        dec(isum[rer],j);       inc(osum[rer],j);
                end;
                inc(k,icnt[rer]*node[rer]^.v-isum[rer]+osum[rer]-ocnt[rer]*node[rer]^.v);
        end;
        cost[st,i]:=min(cost[st,i],k);
end; for i:=1 to rer0 do dispose(que[i]);
end;

function dp:longint;
var i,j,k:longint;
begin
f[0,0]:=0;
for i:=1 to n do
        for j:=1 to m do
                for k:=0 to i-1 do
                        f[i,j]:=min(f[i,j],f[k,j-1]+cost[k+1,i]);
exit(f[n,m]);
end;

function init:longint;
var i,j,k:longint;
begin
fillchar(cost,sizeof(cost),$3f);
fillchar(f,sizeof(f),$3f); readln(n,m);
if (n=0)and(m=0) then exit(-1)
else if (m>=n) then init:=1 else init:=0;
for i:=1 to n do read(s[i]); readln;
end;

procedure work;
var i,j:longint;
begin
for i:=1 to n do s[i]:=s[i]-i;
for i:=1 to n do getcost(i);
for i:=1 to n do s[i]:=-s[i]-(i<<1);
for i:=1 to n do getcost(i);
writeln(dp);
end;

begin
while not seekeof do begin
        leftheap_init(0);
        case init of
                -1:break;
                0:work;
                1:writeln(0);
        end;
end;
end.