Description

硬幣購物一共有4種硬幣。面值分別為c1,c2,c3,c4。某人去商店買東西，去了tot次。每次帶di枚ci硬幣，買si的價值的東西。請問每次有多少種付款方法。
Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
Output

每次的方法數
Sample Input
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
Sample Output
4
27
數據規模
di,s<=100000
tot<=1000

?

每一次都做一次多重背包跟定是不行的，這個先預處理一下，然后可以用容斥原理O（1）回答

我們可以這樣用容斥，先算出沒有限制錢幣數量的方案數，記為f[i]，表示沒有限制，總價值為i的方案數，然后減去至少一種錢幣超過限制的方案數，加上至少兩種錢幣超過限制的方案數，減去至少三種錢幣超過限制的方案數，最后加上四種錢幣都超過限制的方案數，第i種錢幣超過限制就是第i種錢幣至少用了di+1個（例：第1種錢幣超過限制的方案數就是f[s-c[1]*(d1+1)]）

犯了一個傻逼錯誤

求f[i]的時候我是這么求的

1 for i:=1 to maxs do 2 for j:=1 to 4 do 3 inc(f[i],fn(i-c[j]));

然后理所當然的爆了int64

為了不重復計算方案，所以應該以j為階段（話說動態規劃的階段是什么早就忘了），就像這樣

1 for j:=1 to 4 do 2 for i:=1 to maxs do 3 inc(f[i],fn(i-c[j]));

?

吐槽：

R：容斥原理是什么？我們學過嗎？

X：學過啊

R：額，這算學過嗎，我只記得老師叫我們用容斥寫在100以內是2,3,5的倍數的數有多少，然后要我們查公式，這TM有什么意思，這個題有必要做嗎，換個例題不行啊

當時我就想啊，容斥這么垃圾（不要打我......），我就直接跳過了，沒想到容斥原來用處挺大的啊（當時講的那個例題毫無吸引力好嗎）

1 const 2 maxs=100010; 3 var 4 f:array[0..maxs]of int64; 5 c:array[1..4]of longint; 6 n:longint; 7 ans:int64; 8 9 function fn(x:longint):int64; 10 begin 11 if x>=0 then exit(f[x]); 12 exit(0); 13 end; 14 15 procedure main; 16 var 17 i,j,d1,d2,d3,d4,s:longint; 18 begin 19 for i:=1 to 4 do 20 read(c[i]); 21 f[0]:=1; 22 for j:=1 to 4 do 23 for i:=1 to maxs do 24 inc(f[i],fn(i-c[j])); 25 read(n); 26 for i:=1 to n do 27 begin 28 read(d1,d2,d3,d4,s); 29 ans:=fn(s); 30 dec(ans,fn(s-c[1]*(d1+1))); 31 dec(ans,fn(s-c[2]*(d2+1))); 32 dec(ans,fn(s-c[3]*(d3+1))); 33 dec(ans,fn(s-c[4]*(d4+1))); 34 inc(ans,fn(s-c[1]*(d1+1)-c[2]*(d2+1))); 35 inc(ans,fn(s-c[1]*(d1+1)-c[3]*(d3+1))); 36 inc(ans,fn(s-c[1]*(d1+1)-c[4]*(d4+1))); 37 inc(ans,fn(s-c[2]*(d2+1)-c[3]*(d3+1))); 38 inc(ans,fn(s-c[2]*(d2+1)-c[4]*(d4+1))); 39 inc(ans,fn(s-c[3]*(d3+1)-c[4]*(d4+1))); 40 dec(ans,fn(s-c[2]*(d2+1)-c[3]*(d3+1)-c[4]*(d4+1))); 41 dec(ans,fn(s-c[1]*(d1+1)-c[3]*(d3+1)-c[4]*(d4+1))); 42 dec(ans,fn(s-c[1]*(d1+1)-c[2]*(d2+1)-c[4]*(d4+1))); 43 dec(ans,fn(s-c[1]*(d1+1)-c[2]*(d2+1)-c[3]*(d3+1))); 44 inc(ans,fn(s-c[1]*(d1+1)-c[2]*(d2+1)-c[3]*(d3+1)-c[4]*(d4+1))); 45 writeln(ans); 46 end; 47 end; 48 49 begin 50 main; 51 end. View Code

?

轉載于:https://www.cnblogs.com/Randolph87/p/3649744.html

總結

以上是生活随笔為你收集整理的1042: [HAOI2008]硬币购物 - BZOJ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。