ZigZagK

Never give up fighting!

[DP+组合]LOJ2538(PKUWC 2018)【Slay the Spire】题解

题目概述

\(n\) 张攻击牌(造成攻击牌数值的伤害)和 \(n\) 张强化牌(攻击牌伤害均 \(\times\) 强化牌数值),从中抽出 \(m\) 张并选出最优秀的 \(K\) 张打出,求所有方案造成的伤害之和。

解题报告

容易证明能打强化牌就打强化牌,然后再打攻击牌是最优秀的(除非抽到的强化牌超过 \(K\) 张,那么肯定要留一张攻击牌)。所以我们可以定义 \(F(i,j)\) 为抽到了 \(i\) 张攻击牌选了 \(j\) 张打出的方案和,\(G(i,j)\) 为抽到了 \(i\) 张强化牌选了 \(j\) 张打出的方案和。然后答案就是: \[
\sum_{i=0}^{m}\begin{cases}F(m-i,K-i)G(i,i)&i\le K-1\\F(m-i,1)G(i,K-1)&i>K-1\end{cases}
\]
但是 \(F(x,y)\)\(G(x,y)\) 怎么求?对攻击牌和强化牌排序之后,我们可以强制在前 \(i\) 个中选 \(j\) 个,记为 \(f(i,j),g(i,j)\) ,然后就可以直接组合数算出方案为 \(n-i\choose x-y\) ,则 \(F(x,y)=\sum f(i,j){n-i\choose x-y},G(x,y)\) 同理。

示例程序

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注