CF1854E Games Bundles 题解

发布时间 2023-10-25 10:48:13作者: blueparrot

乱搞题

设个 \(dp[i]\) 表示和为 \(i\) 的子序列个数,那么转移是容易的, \(dp[j]+=dp[j-i]\) ,然后就判下 \(dp[60]+dp[60-i]\) 是否大于 \(m\) ,发现这样子搞对于比较大的数可能达不到 \(m\) 的限制,因为这样子转移,默认的是一个数只选一次,但是我们可以重复选,这启发我们需要设定一个值 \(P\),让每个数选 \(P\) 次。直觉判断这题答案解很多,所以我们把 \(P\)\([1,60]\) 范围随机一下,一直到 \(dp[60]==m\) 的时候就找到了答案。

时间复杂度,发现随机次数不会太大,或者你也可以穷举,上界是 \(O(60^3)\)

然后不知道为什么就过了。

仅供参考,训练意义不大