Sửa hàng rào

Chọn HSG quốc gia - Quảng Trị 2012 - vòng 1 - Bài 2/3
Mèo Tom vừa chuyển đến ngôi nhà mới bên một bãi biển xinh đẹp của miền Trung. Mọi thứ trong ngôi nhà đều rất vừa ý với chú mèo, ngoại trừ bức tường rào màu xanh bao quanh ngôi nhà. Bức tường rào được ghép lại từ N thanh gỗ xếp liền nhau, chiều cao của các thanh gỗ là các số nguyên dương a1, a2, ..., aN. Sau khi tham khảo ý kiến của kiến trúc sư, Tom quyết định thay đổi chiều cao của các thanh gỗ của bức tường rào thành b1, b2, ..., bN. (Không nhất thiết ai phải đổi thành bi). Chuột Jerry, một chủ thầu xây dựng tài ba, cho biết chi phí tăng chiều cao của một thanh gỗ bất kì lên một đơn vị là X miếng pho-mát và chi phí giảm chiều cao của một thanh gỗ bất kì xuống một đơn vị là Y miếng pho-mát.
Yêu cầu: Hãy tính chi phí thấp nhất cần phải sửa hàng rào theo ý muốn của mèo Tom là bao nhiêu miếng pho-mát?
Dữ liệu: Đọc vào từ tệp văn bản REP.INP có cấu trúc như sau:
- Dòng đầu ghi lần lượt ba số N, X ,Y (3 <= N <=10^4 ;0 <= X,Y <=10^3 ) ;
- N dòng tiếp theo, dòng thứ i ghi lần lượt hai số ai và bi (0 <=ai, bi <= 10^22 );
- Các số trên cùng một dòng cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản REP.OUT gồm một số duy nhất là chi phí tìm được.
Ví dụ:
REP.INP      REP.INP
3 6 5                  11
3 1
1 2
1 2
Phương án tối ưu trong ví dụ trên được thực hiện như sau:
- thanh gỗ thứ nhất chiều cao ban đầu 3 sửa thành 2 mất chi phí là 5 miếng pho-mát;
- thanh gỗ thứ hai chiều cao ban đầu 1 giữ nguyên 1 mất chi phí là 0 miếng pho-mát;
- thanh gỗ thứ ba chiều cao ban đầu 1 sửa thành 2 mất chi phí là 6 miếng pho-mát. + chr$(13) + chr$(10) + _
Lưu ý: Có 40 % số test với N <= 9 ; 70 % số test với N <=18 .

                                                           Lời giải tham khảo

Var + chr$(13) + chr$(10) + _
   a,b,c: array[1..20] of integer;
   m,n: array[1..20] of boolean;
   i,j,g,k,x,y,gia,vt,min,pm: Integer;
   f: text;
BEGIN
   assign(f,'rep.inp');
   reset(f);
        readln(f,k,x,y);
        for i:=1 to k do readln(f,a[i],b[i]);
   close(f);
   for i:=1 to k do
     begin
        m[i]:=true; n[i]:=true;
     end;
   for i:=1 to k do
      if m[i] then
         for j:=1 to k do
            if (n[j]) and m[i] and (a[i]=b[j]) then
               begin
                   m[i]:=false; n[j]:=false;
               end;
   for i:=1 to k do
      if m[i] then
       begin
        for j:=1 to k do
           if n[j] then min:=abs(a[i]-b[j])*x*y;
        for j:=1 to k do
          if n[j] then
            begin
               if a[i]>b[j] then gia:=(a[i]-b[j])*y
               else gia:=(b[j]-a[i])*x;
               if min> gia then
                  begin
                     min:=gia;
                     vt:=j;
                  end;
            end;
          m[i]:=false;
          n[vt]:=false;
          pm:=pm+gia;
       end;
   writeln('Mieng phomat can mat la: ',pm);
   readln;
END.