记录编号	21704	评测结果	AAWAWTTTTT
题目名称	奇怪的监狱	最终得分	30
用户昵称	donny	是否通过	未通过
代码语言	Pascal	运行时间	5.007 s
提交时间	2010-11-12 19:55:07	内存使用	3.93 MiB

program prison;
var
  i,j,k:longint;
  a:array[1..1000]of boolean;
  e:array[1..100]of longint;
  n,m:longint;
  f:array[1..1000,1..1000]of longint;
  b:boolean;
function min(const x,y:longint):longint;
begin
  if x>y then exit(y)
  else exit(x);
end;
begin
  assign(input,'prison.in');
  reset(input);
  assign(output,'prison.out');
  rewrite(output);
  readln(n,m);
  for i:=1 to m do
  begin
    read(e[i]);
    a[e[i]]:=true;
  end;
  for i:=1 to n do
    for j:=1 to n do
      f[i,j]:=maxint;
  for i:=1 to n do
  begin
    f[i,i]:=0;
    if i<n then
    begin
      if a[i]or a[i+1] then
        f[i,i+1]:=1
          else f[i,i+1]:=0;
    end;
  end;
  for k:=2 to n-1 do
    for i:=1 to n-k do
    begin
    b:=true;
      for j:=1 to m do
        if (e[j]>i)and(e[j]<i+k) then
        begin
          f[i,i+k]:=min(f[i,i+k],f[i,e[j]-1]+f[e[j]+1,i+k]+k);
          b:=false;
        end
        else
          if e[j]>=i+k then
            break;
    if b then f[i,i+k]:=0;
    end;
  writeln(f[1,n]);
  close(input);
  close(output);
end.