比赛 |
20120707 |
评测结果 |
WWWWTWWWWWWWWWWWWWWW |
题目名称 |
修整数列 |
最终得分 |
0 |
用户昵称 |
zhangchi |
运行时间 |
2.457 s |
代码语言 |
Pascal |
内存使用 |
1.46 MiB |
提交时间 |
2012-07-07 11:53:58 |
显示代码纯文本
type
node=record
x,y:integer;
next:longint;
end;
var
n,a,b,i,j,ans,min,temp,mark,sum,tot,time,max:longint;
p:boolean;
c:array[1..200] of longint;
d:array[-200..200,1..2] of longint;
e:array[1..200,1..2] of longint;
f:array[-200..200] of longint;
g:array[1..170000] of node;
procedure work;
begin
sum:=0;
for i:=1 to n do
if d[c[i],1]>10000000 then
begin
writeln(-1);
close(input); close(output);
halt;
end
else
begin
e[i,1]:=d[c[i],1];
e[i,2]:=d[c[i],2];
end;
for i:=1 to n do
begin
while e[i,1]<>0 do begin
if e[i,1]>0 then
begin
min:=e[i,1];
p:=true;
for j:=i+1 to n do
if e[j,1]>0 then
begin if e[j,1]<min then min:=e[j,1]; end
else begin p:=true; break; end;
if p=false then mark:=j-1 else mark:=j;
if i+1>n then mark:=i;
for j:=i to mark do
dec(e[j,1],min);
inc(sum,min);
end
else
begin
min:=e[i,1];
p:=true;
for j:=i+1 to n do
if e[j,1]<0 then
begin if e[j,1]>min then min:=e[j,1]; end
else begin p:=false; break; end;
if p=false then mark:=j-1 else mark:=j;
if i+1>n then mark:=i;
for j:=i to mark do
dec(e[j,1],min);
inc(sum,abs(min));
end;
end;
while e[i,2]<>0 do begin
if e[i,2]>0 then
begin
min:=e[i,2];
p:=true;
for j:=i+1 to n do
if e[j,2]>0 then
begin if e[j,2]<min then min:=e[j,2]; end
else begin p:=false; break; end;
if p=false then mark:=j-1 else mark:=j;
if i+1>n then mark:=i;
for j:=i to mark do
dec(e[j,2],min);
inc(sum,min);
end
else
begin
min:=e[i,2];
p:=true;
for j:=i+1 to n do
if e[j,2]<0 then
begin if e[j,2]>min then min:=e[j,2]; end
else begin p:=false; break; end;
if p=false then mark:=j-1 else mark:=j;
if i+1>n then mark:=i;
for j:=i to mark do
dec(e[j,2],min);
inc(sum,abs(min));
end;
end;
end;
end;
procedure dfs(k:longint);
var
t:longint;
begin
if k>=max+1 then
begin
work;
if sum<ans then ans:=sum;
exit;
end;
inc(time);
if time>50000000 div n div n then
begin
writeln(ans);
close(input); close(output);
halt;
end;
t:=f[k];
while t<>0 do
begin
d[k,1]:=g[t].x;
d[k,2]:=g[t].y;
dfs(k+1);
t:=g[t].next;
end;
end;
begin
assign(input,'seq.in'); reset(input);
assign(output,'seq.out'); rewrite(output);
readln(n,a,b);
if n>200 then begin writeln(-1); close(input); close(output); halt; end;
for i:=1 to n do
begin read(c[i]); if abs(c[i])>max then max:=abs(c[i]); end;
fillchar(d,sizeof(d),$7F div 2);
for i:=-max to max do
for j:=-max to max do
begin
temp:=i*a+j*b;
if abs(temp)<=max then
begin
inc(tot);
g[tot].next:=f[temp];
f[temp]:=tot;
g[tot].x:=i;
g[tot].y:=j;
end;
end;
ans:=maxlongint;
dfs(-max);
if ans=maxlongint then writeln(-1) else writeln(ans);
close(input); close(output);
end.