[BZOJ1042/Luogu1450][HAOI2008]硬币购物(动态规划,容斥原理)

发布于 2018-04-03  150 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1042/Luogu1450][HAOI2008]硬币购物(动态规划,容斥原理)

Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买s
i的价值的东西。请问每次有多少种付款方法。

Tag

动态规划,容斥原理

解决思路

考虑当没有硬币的数量限制时怎么做,设\(F[i][j]\)表示前i种硬币凑出j元的方案数,这个可以用类似背包的方式预处理出来。

然后考虑限制了数量怎么做。无非是不限制数量的-强制一种一定超过限制+强制两种一定超过限制-强制三种+强制四种。利用容斥原理求解。

至于如何强制某一种面值为i硬币一定购买c个呢?用总数减去i*c就可以得到了。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1042/Luogu1450][HAOI2008]硬币购物(动态规划,容斥原理)


HNCJ OIer