记录编号	48342	评测结果	AAAAAAAAAA
题目名称	奇怪的监狱	最终得分	100
用户昵称	张来风飘	是否通过	通过
代码语言	Pascal	运行时间	0.011 s
提交时间	2012-11-05 16:01:15	内存使用	0.25 MiB

program Project1;
var f:array[0..150,0..150] of longint;
    num,a,sum:array[0..150] of longint;
    n,m:longint;
procedure init;
var i,j:longint;
begin
     assign(input,'prison.in');reset(input);
     assign(output,'prison.out');rewrite(output);
     read(n,m);
     for i:=1 to m do read(a[i]);
     a[0]:=0;a[m+1]:=n+1;
     for i:=1 to m+1 do
         for j:=1 to m+1 do f[i,j]:=999999999;
     for i:=1 to m+1 do
     begin
          num[i]:=a[i]-a[i-1]-1;
          f[i,i]:=0;
     end;
     sum[0]:=0;
     for i:=1 to m+1 do
         sum[i]:=sum[i-1]+num[i];
end;
function min(a,b:longint):longint;
begin
     if a<b then exit(a) else exit(b);
end;
procedure main;
var len,i,j,k:longint;
begin
     for len:=2 to m+1 do
         for i:=1 to m-len+2 do
         begin
              j:=len+i-1;
              for k:=i to j-1 do
              begin
                   f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]+sum[j]-sum[i-1]+len-2);
              end;
         end;
     writeln(f[1,m+1]);
     close(input);
     close(output);
end;
begin
     init;
     main;
end.