比赛 |
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.