原来背包问题还有这种解法，动态规划+容斥原理。由于有tot次询问，如果对每次询问单独都做一次多重背包问题，会超时。有一种一次预处理，每次询问只有O(1)的神奇解法：容斥原理。
设F[i]为不考虑每种硬币的数量限制的情况下，得到面值i的方案数。则状态转移方程为
F[i]=Sum{F[i-C[k]] | i-C[k]>=0 且 k=1..4}
为避免方案重复，要以k为阶段递推，边界条件为F[0]=1，这样预处理的时间复杂度就是O(S)。
接下来对于每次询问，奇妙的解法如下：根据容斥原理，答案为 得到面值S的超过限制的方案数 – 第1种硬币超过限制的方案数 – 第2种硬币超过限制的方案数 – 第3种硬币超过限制的方案数 – 第4种硬币超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。
当第1种硬币超过限制时，只要要用到D[1]+1枚硬币，剩余的硬币可以任意分配，所以方案数为 F[ S - (D[1]+1)*C[1] ]，当且仅当(S – (D[1]+1)*C[1])>=0，否则方案数为0。其余情况类似，每次询问只用问16次，所以询问的时间复杂度为O(1)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | /* * Problem: HAOI2008 coin * Author: Guo Jiabao * Time: 2009.4.15 21:54 * State: Solved * Memo: 动态规划 容斥原理 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> const int MAXN=100001; using namespace std; int D[5],C[5],T,S; long long F[MAXN],Ans; void init() { freopen("coin.in","r",stdin); freopen("coin.out","w",stdout); scanf("%d%d%d%d%d",&C[1],&C[2],&C[3],&C[4],&T); } inline long long Fn(int a) { return a>=0?F[a]:0; } void printint64(long long a) { int m=100000000; if (a<=m) printf("%dn",a); else { printf("%d",Ans/m); printf("%08dn",Ans%m); } } void solve() { int i,j; F[0]=1; for (j=1;j<=4;j++) for (i=1;i<MAXN;i++) if (i-C[j]>=0) F[i] += F[i-C[j]]; for (i=1;i<=T;i++) { scanf("%d%d%d%d%d",&D[1],&D[2],&D[3],&D[4],&S); Ans =Fn( S ); Ans-=Fn( S - (D[1]+1)*C[1] ); Ans-=Fn( S - (D[2]+1)*C[2] ); Ans-=Fn( S - (D[3]+1)*C[3] ); Ans-=Fn( S - (D[4]+1)*C[4] ); Ans+=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] ); Ans+=Fn( S - (D[1]+1)*C[1] - (D[3]+1)*C[3] ); Ans+=Fn( S - (D[1]+1)*C[1] - (D[4]+1)*C[4] ); Ans+=Fn( S - (D[2]+1)*C[2] - (D[3]+1)*C[3] ); Ans+=Fn( S - (D[2]+1)*C[2] - (D[4]+1)*C[4] ); Ans+=Fn( S - (D[3]+1)*C[3] - (D[4]+1)*C[4] ); Ans-=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] - (D[3]+1)*C[3] ); Ans-=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] - (D[4]+1)*C[4] ); Ans-=Fn( S - (D[1]+1)*C[1] - (D[3]+1)*C[3] - (D[4]+1)*C[4] ); Ans-=Fn( S - (D[2]+1)*C[2] - (D[3]+1)*C[3] - (D[4]+1)*C[4] ); Ans+=Fn( S - (D[1]+1)*C[1] - (D[2]+1)*C[2] - (D[3]+1)*C[3] - (D[4]+1)*C[4] ); printint64(Ans); } } int main() { init(); solve(); return 0; } |
http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=302
硬币购物
【问题描述】
一共有 4 种硬币,面值分别为 c1,c2,c3,c4 。阿Q带着一些硬币去商店买东西，他带了d1枚第一种硬币,d2枚第二种硬币,d3枚第三种硬币,d4枚第四种硬币,若想买一个价值为s的东西,问阿Q有多少种付coins的方法。
比如 c={1,2,5,10},d={3,2,3,1},s=10,一共有4种方法:
10=1+1+1+2+5
10=1+2+2+5
10=5+5
10=10注意,阿Q可能会去很多次商店,每次带的硬币数量和要买的东西价值可能不一样,你需要对每次都求出方法总数.
【数据输入】
输入文件的第一行是5个整数, c1,c2,c3,c4,tot 分别表示4种硬币的面值和阿Q去商店的次数,下面 tot 行 ,每行5个非负整数,d1,d2,d3,d4,s
【数据输出】
输出有tot行,表示第i次付coins的方法总数,保证答案在int64/long long范围内
【输入样例】
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900【输出样例】
4
27【数据范围】
（1）100%的数据,d1,d2,d3,d4,s<=1,00,000
（2）30%的数据,tot<=50
（3）100%的数据,tot<=1000
参见CEOI2004-2 SWEETS
[回复]
面值S的超过限制的方案数 – 第1种硬币超过限制的方案数 – 第2种硬币超过限制的方案数 – 第3种硬币超过限制的方案数 – 第4种硬币超过限制的方案数 + 第1,2种硬币同时超过限制的方案数 + 第1,3种硬币同时超过限制的方案数 + …… + 第1,2,3,4种硬币全部同时超过限制的方案数。
这句话没有问题吗？
面值S的超过限制的方案数不就是等于后面的一大堆吗？
[回复]
BYVoid 回复:
三月 5th, 2010 at 12:52:12
這是容斥原理，“面值S的超过限制的方案数”當然不等於後面的
[回复]
sevenkplus 回复:
三月 12th, 2010 at 17:33:27
这句话没有问题，不解释。
[回复]
Orz
第一次看到这种方法~
另：是不是所有的反斜杠都被过滤了？
[回复]