题目链接:https://www.luogu.com.cn/problem/P5299
有\(2n\)张牌,
\(n\)张强化牌,每张上有一个正整数\(x(x>1)\),如果使用后之后的每一张攻击牌伤害都会乘上\(x\)。
\(n\)张攻击牌,每张上有一个正整数\(x\),使用后造成\(x\)点伤害。
随机抽上来\(m\)张,然后按照最优策略打出\(k\)张的情况下,求所有情况造成的伤害和。
\(1\leq k\leq m\leq 2n\leq 3000\)
考虑一个最优策略是啥,显然地我们有强化牌肯定优先打出,直到打完或者只剩最后一费。
因为翻倍至少多一倍的伤害,而我们攻击牌肯定是从大往小选,所以不可能一张攻击牌使得伤害翻倍。
先把两种牌按照数组从大到小排序
我们可以分为两种情况讨论
打出\(k-1\)张强化牌和一张攻击牌
打出\(<k-1\)张强化牌和若干张攻击牌
第一种情况我们设\(f_i\)表示选出了\(i\)张强化牌的所有方案中前\(k\)张牌乘积的和。
然后枚举一个在\(k-1\sim m\)之间的数字\(i\)表示抽到了\(i\)张强化牌,然后再枚举攻击力最大的一张攻击牌,剩下的方案用组合数计算即可。
第二种情况比较麻烦,同样的设\(f_{0,i}\)表示抽了\(i(i<k)\)张强化牌的所有方案中所有牌的乘积和。然后设\(f_{i,j}\)表示总共选了\(i\)张攻击牌和强化牌,打出了前\(k\)张强化牌和攻击牌时所有强化牌乘积的和,\(g_{i,j}\)则表示造成的伤害和。
然后转移即可。
时间复杂度:\(O(nm)\)