比赛 20101101 评测结果 AAAAAWWWWW
题目名称 奇怪的监狱 最终得分 50
用户昵称 张来风飘 运行时间 0.020 s
代码语言 Pascal 内存使用 0.18 MiB
提交时间 2012-11-05 11:41:42
显示代码纯文本
program Project1;
var a,b,pre,next:array[0..101] of longint;
    sum:array[0..1001] of longint;
    v:array[0..101] of boolean;
    map:array[0..101,0..101] of boolean;
    ans,n,m:longint;
procedure init;
var i,j,y: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]);
     for i:=1 to m do
         for j:=i+1 to m do if a[i]>a[j] then
         begin
              y:=a[i];a[i]:=a[j];a[j]:=y;
         end;
end;
procedure culculate;
var i,tans,temp,k,j:longint;
begin
     //for i:=1 to m do write(a[i],' ');writeln;
     fillchar(map,sizeof(map),true);
     for i:=1 to n do map[i,i]:=false;
     tans:=0;
     for i:=1 to m do
     begin
          temp:=0;
          for j:=1 to n do
              if map[a[i],j] then
                   inc(temp);
          for j:=1 to a[i] do
              for k:=a[i] to n do
              begin
                  map[j,k]:=false;
                  map[k,j]:=false;
              end;
          //writeln(temp);
          inc(tans,temp);
     end;
     if tans<ans then ans:=tans;
end;
procedure dfs(depth:longint);
var i:longint;
begin
     if depth>m then
     begin
          culculate;
          exit;
     end;
     for i:=1 to m do if not v[i] then
     begin
          a[depth]:=b[i];
          v[i]:=true;
          dfs(depth+1);
          v[i]:=false;
     end;
end;
procedure points;
var i:longint;
begin
     for i:=1 to m do b[i]:=a[i];
     fillchar(v,sizeof(v),0);
     ans:=maxlongint;
     dfs(1);
     writeln(ans);
     halt;
end;
procedure main;
var i,k,min,u:longint;
begin
     if m<=10 then points;
     for i:=1 to n do sum[i]:=i;
     for i:=1 to m do
     begin
          pre[i]:=a[i-1];next[i]:=a[i+1]-1;
          if i=1 then pre[i]:=0;
          if i=m then next[i]:=n;
     end;
     k:=0;//释放次数
     ans:=0;
     fillchar(v,sizeof(v),0);
     while k<m do
     begin
          inc(k);
          min:=maxlongint;
          for i:=1 to m do if not v[i] then
          begin
               if sum[next[i]]-sum[pre[i]]-1<min then
               begin
                    min:=sum[next[i]]-sum[pre[i]]-1;
                    u:=i;
               end;
          end;
          v[u]:=true;//write(a[u],' ');
          inc(ans,min);
          if u>1 then next[u-1]:=next[u];
          if u<n then pre[u+1]:=pre[u];
     end;
     writeln(ans);
    //a[1]:=3;a[2]:=11;a[3]:=6;a[4]:=14;ans:=maxlongint;culculate;
    //writeln(ans);
     close(input);
     close(output);
end;
begin
     init;
     main;
end.