CF1740F Conditional Mix

CF1740F


第一眼看上去,最后肯定是一个 \(n^2\) 的背包问题。但是肯定不是所有集合都符合条件的。

可以按照从大到小的顺序加入数,令 \(f(i,l)\) 表示集合里 \(i\) 个数,总和为 \(l\) 的方案数。

那么可以得到一个结论:按照这样选数的话,对于 \(i\) 个数的集合,合法的集合当且仅当总和不超过上界,上界是好算的,对于每一类的数,如果出现次数小于 \(i\),贡献为 \(cur_i\),否则贡献为 \(i\)

这个做法感觉是最简单的,但是这一题也有很多种其他的思考方法,欢迎补充。

时间复杂度:\(\Theta(n^2\log n)\)


CF1740F Conditional Mix
https://shmilyty.cf/cf1740f/
作者
ShmilyTY
发布于
2022年10月30日
许可协议