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

program linka;
type
  integer=longint;
const
  maxq=110;
var
  n,q:integer;
  p:array[1..maxq] of integer;
  sum:array[0..maxq] of integer;
  d:array[1..maxq,1..maxq] of integer;

  procedure Fopen;
  begin
    assign(input,'linka.in'); reset(input);
    assign(output,'linka.out'); rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input); close(output);
  end;

  procedure Sort;
  var
    i,j:integer;
    tmp:integer;
  begin
    for i:=1 to q-1 do
    for j:=i+1 to q do
      if p[i]>p[j] then
      begin
        tmp:=p[i]; p[i]:=p[j]; p[j]:=tmp;
      end;
  end;

  procedure Init;
  var
    i:integer;
  begin
    readln(n,q);
    for i:=1 to q do read(p[i]);
    Sort;
    sum[0]:=-1;
    for i:=1 to q do sum[i]:=p[i]-1;
    sum[q+1]:=n;
    n:=q+1;
  end;

  procedure Dp;
  var
    l,r,m,k:integer;
  begin
    for k:=1 to n do d[k,k]:=0;
    for k:=2 to n do
      for l:=1 to n-k+1 do
      begin
        r:=l+k-1;
        d[l,r]:=maxlongint shr 2;
        for m:=l to r-1 do
          if d[l,m]+d[m+1,r]<d[l,r] then
            d[l,r]:=d[l,m]+d[m+1,r];
        inc(d[l,r],sum[r]-sum[l-1]-2);
      end;
    writeln(d[1,n]);
  end;

begin
  Fopen;
  Init;
  Dp;
  Fclose;
end.