BZOJ 1042 [HAOI2008] 硬币购物

发布于 2017-06-14  143 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1042

题意:4 种硬币面值分别为 c1,c2,c3,c4。买东西 tot 次。每次带 di 枚 ci 硬币,买 si 的价值的东西。每次有多少种付款方法


\(F_s\) 表示不考虑限制总方案数,tot 表示不满足某种/某些限制的方案数,显然 \(ans=F_s-tot\)
\(F_s\) 直接 dp 获得
$$F_j=\sum_{i=1}^{4}F_{j-c_i}$$
考虑容斥求得 tot
tot=(第 1 种超限方案数+...+第 4 种超限方案数)-(第 12 种超限方案数+...+第 34 种超限方案数)+(第 123 种超限方案数+...+第 234 种超限方案数)-(第 1234 种超限方案数)
设目前第 i 种硬币超限 即满足强制使用 d[i]+1 个该硬币 其余随意使用 那么这个方案数可以通过 F 数组直接获得 即 F[sum-(d[i]+1)*c[i]]

 


一个非常弱的准退役OIER