传送门： P1450 [HAOI2008] 硬币购物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1450 题干： 题目描述 共有 4 种硬币。面值分别为 c1​,c2​,c3​,c4​。 某人去商店买东西，去了 n 次，对于每次购买，他带了 di​ 枚 种硬币，想购买 s 的价值的东西。请问每次有

思路 完全背包：预处理出不限制硬币数量的方案数。 dp[0]=1;dfor(i,1,4) dfor(j,c[i],(int)1e5) dp[j]+=dp[j-c[i]]; 容斥 不限制数量的方案数 − - − 超出限制的方案数 = 符合限制的方案数 。考虑第 i i i 种硬币超出数量限制的方案数。强制支付 d i + 1 d_i+1 di​+1 个 i i i 种硬币，价值为