power.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

program E1_10; {power}
type arr=array[1..100] of 0..1;
var d,w:array[1..100] of integer;
    n,c,i,t:longint;
    min:longint;
    bb:arr;
    input,output:text;

procedure search(bp,t,wt,fx:integer;bb:arr);
var i,j,tl,tr:longint;
    wl,wr:longint;
    b:arr;
begin
   for i:=1 to n do b[i]:=bb[i];
   if fx=1 then
    begin
     i:=bp+1; wr:=wt; tr:=t+d[i]-d[i-1];
     while b[i]=0 do
      begin
       i:=i+1; tr:=tr+d[i]-d[i-1]
      end;
      wr:=wr+tr*w[i]; b[i]:=0;
      if wr>=min then exit
                 else
                  if (i<n) then
                    begin
                     search(i,tr,wr,1,b);
                     search(i,tr,wr,-1,b);
                    end
                    else
                     begin
                      j:=n;
                      while (j>1) and (wr<min) do
                       begin
                        j:=j-1;
                        tr:=tr+(d[j+1]-d[j]);
                        wr:=wr+b[j]*tr*w[j];
                       end;
                      if (j=1) and (wr<min) then min:=wr;
                     end;
    end
     else
      begin
       i:=bp-1;wl:=wt;tl:=t+d[i+1]-d[i];
       while b[i]=0 do
        begin
        i:=i-1; tl:=tl+d[i+1]-d[i];
        end;
       wl:=wl+tl*w[i];b[i]:=0;
       if wl>=min then exit
        else
          if i>1 then
              begin
               search(i,tl,wl,1,b);
               search(i,tl,wl,-1,b);
              end
           else
             begin
               j:=1;
               while (j<n) and (wl<min) do
                begin
                 j:=j+1;
                 tl:=tl+(d[j]-d[j-1]);
                 wl:=wl+b[j]*tl*w[j];
                end;
               if (j=n) and (wl<min) then min:=wl;
              end;
      end;
end;

begin {main}
 assign(input,'power.in');reset(input);
 readln(input,n,c);
 for i:=1 to n do readln(input,d[i],w[i]);
 close(input);
 for i:=c-1 downto 1 do
 begin
  t:=t+d[i+1]-d[i];
  min:=min+t*w[i];
 end;
 t:=2*t;
 for i:=c+1 to n do begin t:=t+d[i]-d[i-1];min:=min+t*w[i];end;
 for i:=1 to n do bb[i]:=1;
 bb[c]:=0;
 search(c,0,0,1,bb); search(c,0,0,-1,bb);
 assign(output,'power.out'); rewrite(output);
 writeln(output,min); close(output)
end.