比赛 20101101 评测结果 AAAAAAAAAA
题目名称 奇怪的监狱 最终得分 100
用户昵称 亟隐 运行时间 0.010 s
代码语言 Pascal 内存使用 0.21 MiB
提交时间 2012-11-05 09:42:49
显示代码纯文本
var     f:array[0..110,0..110]of longint;
        a:array[0..110]of longint;
        n,m,i,j,k,p:longint;

procedure init;
begin
        readln(m,n);
        for i:=1 to n do read(a[i]);
        for i:=1 to n do
                for j:=i+1 to n do if a[i]>a[j] then
                begin
                        k:=a[i]; a[i]:=a[j]; a[j]:=k;
                end;
        a[0]:=0; a[n+1]:=m+1;
        for i:=1 to n do f[i,i]:=a[i+1]-a[i-1]-2;
end;

function min(x,y:longint):longint;
begin
        if x>y then exit(y) else exit(x);
end;

procedure work;
begin
        for j:=1 to n do
                for i:=1 to n-j+1 do
                begin
                        m:=i+j; f[i,m]:=maxlongint; p:=a[m+1]-a[i-1]-2;
                        for k:=i to m do f[i,m]:=min(f[i,m],f[i,k-1]+f[k+1,m]+p);
                end;
        writeln(f[1,n]);
end;

begin
assign(input,'prison.in');reset(input);
assign(output,'prison.out');rewrite(output);
        init;
        work;
close(input); close(output);
end.