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