记录编号	39348	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.044 s
提交时间	2012-07-09 15:11:55	内存使用	4.96 MiB

const maxq=101; maxn=1001;
var
 n,q,i,j,t:longint;
 num:array[0..maxq] of longint;
 v:array[0..maxn,0..maxn] of boolean;
 f:array[0..maxn,0..maxn] of longint;
 start,finish:array[0..maxn] of longint;
 procedure dfs(l,r:longint);
 var i,min:longint; flag:boolean;
 begin
  if v[l,r] then exit;
  v[l,r]:=true;
  if l>r then
   begin
    f[l,r]:=0;
    exit;
   end;
  if l=r then
   begin
    f[l,r]:=0;
    exit;
   end;
  min:=maxlongint div 2;
  flag:=true;
  for i:=start[l] to finish[r] do
    begin
     flag:=false;
     dfs(l,num[i]-1); dfs(num[i]+1,r);
     if min>f[l,num[i]-1]+f[num[i]+1,r] then
      min:=f[l,num[i]-1]+f[num[i]+1,r];
    end;
  if flag then f[l,r]:=0;
  if f[l,r]>min+r-l then f[l,r]:=min+r-l;
 end;
begin
 assign(input,'linka.in'); reset(input);
 assign(output,'linka.out'); rewrite(output);
 readln(n,q);
 for i:=1 to q do read(num[i]);
 for i:=1 to q do
  for j:=1 to q-i do
   if num[j]>num[j+1] then
    begin
     t:=num[j]; num[j]:=num[j+1]; num[j+1]:=t;
    end;
 for i:=1 to n do
 begin
  for j:=1 to q do
   if num[j]>i then break;
  if num[j]>i then finish[i]:=j-1 else
   finish[i]:=j;
 end;
 for i:=1 to n do
  begin
   for j:=q downto 1 do
    if num[j]<i then break;
   if num[j]<i then start[i]:=j+1 else
   start[i]:=j;
  end;
 fillchar(f,sizeof(f),$7f div 2);
 dfs(1,n);
 writeln(f[1,n]);
 close(input); close(output);
end.