題意：有4種硬幣，面值分別為c1,c2,c3,c4，然后給出Q組查詢。每組查詢給出5個數d1,d2,d3,d4,v，分別表示面值為ci的硬幣共有di個，然后要求將其湊成總值為v的方案數。

數據范圍大致是c<=1000,Q<=100,d,v<=100000。

如果按照普通分組背包的做法，對每組Q都做一遍DP，那么這個復雜度就會達到10^9的級別，肯定會TLE。我也拿不出太好的辦法，覺得這題DP不出來。

其實，這題不完全是DP，我覺得這個題目的核心是容斥原理。對于每組查詢，算法的復雜度基本上是O(1)這樣的常數級的。

在UVA的論壇里看到了大牛的解釋：

假設現在只有兩種硬幣，我們令N=所有湊出v總值的方案數，N1=第一種面值為c1的硬幣取了超過d1次湊出總值v的方案數，N2=第二種面值為c2的硬幣取了超過d2次湊出總值v的方案數，N12=第一種面值為c1的硬幣取了超過d1次且N第二種面值為c2的硬幣取了超過d2次湊出總值v的方案數。那么對于一組查詢d1,d2,v，合法的方案數就是N-N1-N2+N12.

為了計算這些N，我們利用c1,c2,c3,c4先做一遍背包容量為100000的無限背包，用dp數組記錄方案數。

那么計算N的話，直接算用dp[v]就可以了。

怎么計算N1呢？因為c1硬幣取了超過了d1次，那么我們就假設它取了d1+1次，共取走了(d1+1)*c1價值的硬幣，那么方案數就是dp[v-(d1+1)*c1]。

同理，N2的方案數就是dp[v-(d2+1)*c2]，N12的方案數就是dp[v-(d1+1)*c1-(d2+1)*c2]。然后統計N-N1-N2+N12，就可以得到答案了。

現在問題中的硬幣種類邊成了4個，還是用一樣的原理，這時候答案就是N-N1-N2-N3-N4+N12+N13+N14+N23+N24+N34-N123-N124-N134-N234+N1234，一共16項。

1 #include <cstdio> 2 typedef long long LL; 3 LL dp[100010]; 4 5 int main(){ 6 int c[4],d[4],v,Q,kase; 7 scanf("%d",&kase); 8 while(kase--){ 9 dp[0] = 1; 10 for(int i = 1;i <= 100000;i++) dp[i] = 0; 11 12 for(int i = 0;i < 4;i++) 13 scanf("%d",&c[i]); 14 15 for(int i = 0;i < 4;i++) 16 for(int j = c[i];j <= 100000;j++) 17 dp[j] += dp[j-c[i]]; 18 19 scanf("%d",&Q); 20 21 while(Q--){ 22 LL ans = 0; 23 24 for(int i = 0;i < 4;i++) 25 scanf("%d",&d[i]); 26 27 scanf("%d",&v); 28 29 for(int i = 0;i < 16;i++){ 30 int tmp = v; 31 int flag = 1; 32 for(int j = 0;j < 4;j++){ 33 if(i&(1<<j)){ 34 flag = -flag; 35 tmp -= (d[j]+1) * c[j]; 36 } 37 } 38 if(tmp >= 0) ans += flag * dp[tmp]; 39 } 40 41 printf("%lld\n",ans); 42 } 43 } 44 return 0; 45 } View Code

?

轉載于:https://www.cnblogs.com/zhexipinnong/p/3420455.html

總結

以上是生活随笔為你收集整理的UVA 11259 Coin Changing Again的全部內容，希望文章能夠幫你解決所遇到的問題。

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