QBMARKET – SPOJ

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

Thuật toán:

Gọi  L[j] là số cách mua hàng khi có j đồng .Như vậy khi ta có khi ta mua các mặt hàng từ (1..i-1) hết j đồng và số cách mua là L[j] thì khi xét đến mặt hàng thứ i với k là số lượng mặt hàng i mà ta sẽ mua thì số cách mua hết j+c[i]*k ( S) đồng sẽ tăng thêm một lượng L[j]. Ta có công thức quy hoạch động :

Nếu j+c[i]*k<=S thì L[j+c[i]*k]:=L[j+c[i]*k]+L[j] (j=S..1,i=1..n,k=1..mi). Khởi tạo L[0]=1, L[1..S]=0.

Tại sao vì j+c[i]*k<=S vì nếu lớn hơn S rồi ta không cần quan tâm vì ta chỉ có tối đa S đồng thôi.

Trong qua trình cài đặt ta thấy nếu ta duyệt nếu ta duyệt j tăng dần từ 1 đến S, k tăng dần từ 1 đến mi thì sẽ xảy ra trường hợp như sau:j=0,L[0]=1,i=1,c[1]=1. Đầu tiên k=1 thì L[0+1*1]=L[0]+L[2]=1, k=2 thì L[0+1*2]=L[0]+L[2]=1.
Tăng  j và i giữ nguyên, j=1.Đầu tiên k=1 thì L[1+1*1]=L[1]+L[1]=2 đến đây ta đã thấy vô lí L[2] với i=1 không thể nào bằng 2 được mà L[2]=1. Trường hợp này là do khi j=j1 ta tính L[j1+x], j tăng lên j1+x ta tính L[j1+x+y] ta có

L[j1+x+y]=L[j1+x+y]+L[j1+x] mà khi đó L[j1+x] không còn là số cách mua hết j1+x đồng từ i-1 mặt hàng (1..i-1) mà là mua i mặt hàng (1..i) vì ta vừa tính L[j1+x] khi mua k mặt hàng i mà c[i]*k=x, tất nhiên k>=1.Nói ngắn gọn bạn phải hiểu L[j] trong công thức trên là số cách mua hết j đồng từ i-1 mặt hàng (1..i-1)

Để khắc phục tình trạng này ta duyệt j giảm từ S về 0 .

Code bên dưới nộp sẽ được 85 điểm do chạy quá thời gian. Nếu bài cho time limit 1s thì sẽ được 100 điểm. Tất nhiên thuật toán trên hoàn toàn đúng.

Code:

Const
        fi='';
        fo='';
        maxn=500;
        maxs=100000;
 
Type
        arr1    =array[1..maxn] of longint;
        arr2    =array[0..maxs] of int64;
 
Var
        n,s     :longint;
        c,m     :arr1;
        L       :arr2;
        f       :text;
 
procedure nhap;
var
        i       :longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,s,n);
        for i:=1 to n do readln(f,c[i],m[i]);
        close(f);
end;
 
procedure solution;
var
        i,j,k   :longint;
begin
        L[0]:=1; {Neu co 0 dong thi coi la co mot cach la khong mua gi ca}
        for j:=1 to s do L[j]:=0; { Khoi tao mang L }
        for i:=1 to n do
                for j:=s downto 0 do
                        if L[j]>0 then
                        	for k:=1 to m[i] do
                                if j+k*c[i]<=s then
                                        L[j+c[i]*k]:=L[j]+L[j+c[i]*k];
end;
 
procedure xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,L[s]); {Ket qua nam o L[s]}
        close(f);
end;
 
begin
        nhap;
        solution;
        xuat;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*