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

var
  n,q,i,j,k:longint;
  a,l,r:array[1..100] of longint;
  dp:array[1..100,1..100] of longint;
  function min(x,y:longint):longint;
  begin if x<y then min:=x else min:=y; end;
begin
  assign(input,'linka.in'); reset(input);
  assign(output,'linka.out'); rewrite(output);
  readln(n,q);
  for i:=1 to q do
    read(a[i]);
  l[1]:=1; r[1]:=a[2]-1;
  r[q]:=n; l[q]:=a[q-1]+1;
  for i:=2 to q-1 do
    begin
      l[i]:=a[i-1]+1;
      r[i]:=a[i+1]-1;
    end;
  fillchar(dp,sizeof(dp),$7F div 2);
  for i:=1 to q do
    dp[i,i]:=r[i]-l[i];
  for i:=1 to q-1 do
    dp[i,i+1]:=min(dp[i,i]+r[i+1]-l[i],dp[i+1,i+1]+r[i+1]-l[i]);
  for i:=3 to q do
    for j:=1 to q-i+1 do
      begin
        dp[j,j+i-1]:=min(dp[j,j+i-1],dp[j+1,j+i-1]+r[j+i-1]-l[j]);
        dp[j,j+i-1]:=min(dp[j,j+i-1],dp[j,j+i-2]+r[j+i-1]-l[j]);
        for k:=j+1 to j+i-2 do
          dp[j,j+i-1]:=min(dp[j,j+i-1],dp[j,k-1]+dp[k+1,j+i-1]+r[j+i-1]-l[j]);
      end;
  writeln(dp[1,q]);
  close(input); close(output);
end.