[HAOI2008]硬币购物

题目链接: https://www.luogu.com.cn/problem/P1450

 

如果跑多重背包是O($N10^5log_210^5$)的, 这个效率是稳TLE的

但是发现, 硬币的数量其实很少, 只有4种, 原来这玩意能容斥

 

这是一个计数题, 可以采用总方案数-不合法方案数的操作

我们先用完全背包跑出没有限制的所有情况(总方案数)

设f[i]为装满i的方案数, 假设第j种装了至少d[j]+1种, 那么这个方案肯定是不合法的了

(根据完全背包可以知道d[j]+2包含在d[j]+1中...)

 

那么可以通过这个性质来容斥, 答案就为$f[M]-\sum_S  (-1)^{\sum_{j\in S}}*f[M-\sum_{j\in S} (d[j]+1)c[j]]$

后面这个需要通过容斥原理来计算

 

上一篇:1078 字符串压缩与解压 (20 分)


下一篇:[HAOI2008]玩具取名