V8SCORE – SPOJ

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

Thuật toán:

• (đang cập nhập)

Code:

const   fi='';
        fo='';
        oo=20;
var     i,j,tmp2:longint;
        s,k,n,tong,ss,tmp:longint;
        a:array[1..oo,1..oo] of longint;
        c:array[0..200] of boolean;
        trace:array[0..oo] of longint;
        f:text;
        tim:boolean;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,s,k,n);
    for i:=1 to n do
        for j:=1 to k do read(f,a[i,j]);
    close(f);
end;
function max2(x,y:integer):integer;
begin
    if x>y then max2:=x else max2:=y;
end;
procedure init;
begin
    for i:=1 to n do c[a[i,k]]:=true;
end;
procedure thu(x,y,tong:integer);
var     j,ss:integer;
begin
if not(tim) then
 if y=trace[y-1] then
   begin
        tmp:=tong+(k-y+1)*a[x,y];
        if tmp<=s then
                begin
                        tong:=tong+a[x,y];
                        trace[y]:=a[x,y];
                        for j:=1 to n do thu(j,y+1,tong);
                end;
   end;
 end else
        begin
        if (c[s-tong]) and (s-tong>=trace[k-1]) then
                begin
                trace[k]:=s-tong;
                tim:=true;
                end;
        end;
end;
procedure xuly;
begin
    trace[0]:=-1;
    for i:=1 to n do
    begin
        if tim then exit else
        begin
                fillchar(trace,sizeof(trace),0);
                thu(i,1,0);
        end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    if tim then
    begin
        writeln(f,'YES');
        for i:=1 to k do write(f,trace[i],' ');
    end
        else writeln(f,'NO');
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.