VODIVIDE – SPOJ

Đề bài: http://vn.spoj.com/problems/VODIVIDE/

Thuật toán: Bài này có thể giải bằng phương pháp Quy hoạch động hoặc CTDL Heap. Ở đây giải theo phương pháp Quy hoạch động.

• Gọi F[i,j] là tổng số tiền lớn nhất mà Sơn nhận được khi xét i đồng và Sơn được j đồng

• F[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);

Code:

uses    math;
const   fi='';
        fo='';
        maxn=5000+2;
var     f:array[0..maxn,0..maxn] of longint;
        a,b,cs:array[1..maxn] of longint;
        res:array[1..maxn] of longint;
        dem,n,i,j:Longint;
        free:array[1..maxn] of boolean;
procedure nhap;
begin
    assign(input,fi);reset(Input);
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do read(b[i]);
    close(input);
end;
procedure init;
begin
    for i:=1 to n do cs[i]:=i;
end;
procedure swap(var x,y:longint);
var     w:longint;
begin
    w:=x;x:=y;y:=w;
end;
procedure qs(l,r:longint);
var     i,j,x:longint;
begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
        while xa[j] do dec(j);
        if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    swap(cs[i],cs[j]);
                    inc(i);dec(j);
                end;
    until i>j;
    if il then qs(l,j);
end;
procedure xuly;
begin
    {f[1,0]:=b[1];}
    qs(1,n);
    for i:=2 to n do
        for j:=1 to i div 2 do
                begin
                    f[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);
                end;
end;
procedure trace;
begin
    i:=n; j:=n div 2;
    while (i<>0) and (j<>0) do
        begin
            if f[i,j]=f[i-1,j-1]+b[i] then
                begin
                        inc(dem);
                        res[dem]:=i;
                        free[i]:=true;
                        dec(i);dec(j);
                end else dec(i);
        end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(f[n,n div 2]);
    for i:=1 to dem do
        begin

            for j:=res[i]-1 downto 1 do
                if free[j]=false then
                        begin
                            write(cs[j],' ');
                            free[j]:=true;
                            break;
                        end;
            write(cs[res[i]],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    trace;
    inkq;
end.