题解 P5299 【[PKUWC2018]Slay the Spire】

· · 题解

在博客查看

大致题意： 有n张强化牌a_i和n张攻击牌b_i，每张牌有一个权值（强化牌的权值大于1），每张强化牌能使所有攻击牌的权值乘上这张强化牌的权值，每张攻击牌造成的伤害等于这张攻击牌的权值。现在，以等概率抽出m张牌，并以最优策略使用其中至多k张牌造成最大的伤害。求所有情况下，造成伤害总和。

何为最优策略

这道题看似毫无头绪，因此，我们先要好好推一推性质。

假设现在我们已经选好了m张牌，那么最优策略是什么？

首先，如果我们已经确定要用x张强化牌和y张攻击牌，那么根据贪心的想法，肯定是先使用权值最大的x张强化牌，再使用权值最大的y张攻击牌。

因此我们把a和b分别从大到小排序。

同时，同样依据贪心，我们可以知道答案就是强化牌的乘积乘上攻击牌之和。

然后我们考虑，在什么情况下，把第y张攻击牌换成第x+1张强化牌，与原先答案相比不会变劣。

原先答案是：

\prod_{i=1}^xa_i\cdot\sum_{i=1}^y b_i

变化后的答案是：

\prod_{i=1}^{x+1}a_i\cdot\sum_{i=1}^{y-1}b_i

则两式相减，即为答案的变化量，也就是：

(a_{x+1}-1)\cdot(\prod_{i=1}^xa_i\cdot\sum_{i=1}^{y-1}b_i)-(\prod_{i=1}^xa_i)\cdot b_y

当变化后答案不变劣，说明变化量\ge 0，即：

(a_{x+1}-1)\cdot(\prod_{i=1}^xa_i\cdot\sum_{i=1}^{y-1}b_i)\ge(\prod_{i=1}^xa_i)\cdot b_y

我们把式子中的\prod_{i=1}^xa_i去掉，就得到：

(a_{x+1}-1)\cdot(\sum_{i=1}^{y-1}b_i)\ge b_y

由于题目中说明，强化牌权值大于1，所以a_{x+1}-1\ge 1。

而在y>1时，因为b数组经过了从大到小排序，所以\sum_{i=1}^{y-1}b_i肯定大于等于b_y。

所以我们可以发现，在y>1时，(a_{x+1}-1)\cdot(\sum_{i=1}^{y-1}b_i)\ge b_y是始终成立的。

也就是说，在保有至少一张攻击牌的前提下，肯定是尽量选择强化牌会更优。

这么一来，这道题一下就可做得多了。

预处理

在正式开始解题之前，我们还需要进行预处理，定义几个变量。

设f_{i,j,0}表示在前i张强化牌中选择j张且第i张被选中的所有情况下，这j张牌的乘积之和，g_{i,j,0}表示在前i张攻击牌中选择j张且第i张被选中的所有情况下，这j张牌的和之和。

同时，定义f_{i,j,1}=\sum_{x=1}^if_{x,j,0},g_{i,j,1}=\sum_{x=1}^ig_{x,j,0}来辅助转移。

则不难发现，有转移方程：

f_{i,j,0}=a_i\cdot f_{i-1,j-1,1} f_{i,j,1}=f_{i,j,0}+f_{i-1,j,1} g_{i,j,0}=b_i\cdot C_{i-1,j-1}+g_{i-1,j-1,1} g_{i,j,1}=g_{i,j,0}+g_{i-1,j,1}

注意，g_{i,j,0}的转移中，C_{i-1,j-1}表示在i-1个数中选择j-1个数的方案，即从g_{i-1,j-1,1}转移到g_{i,j,0}共有C_{i-1,j-1}种情况，而每种情况卡牌权值和加上了b_i，就相当于共加上了b_i\cdot C_{i-1,j-1}。

至于这些东西究竟有什么用，待会儿你就会知道了。

组合数学

接下来，就是分类讨论+推式子啦。

第一类：当m张牌中，强化牌的数量小于k-1张时。

此时必然是选上所有的强化牌，然后选上权值最大的一些攻击牌。

不难发现，其实等于k-1张时也符合这一类情况的操作方案，但为了方便起见，我们把等于k-1的情况放入另一类情况中中。

对于这一种情况，我们枚举i,j分别表示强化牌有i张和最后被选中的攻击牌是第j张。

在强化牌中选择i张的所有合法情况下的乘积之和，其实就是f_{n,i,1}。

而强化牌中选择i张，攻击牌中就要选择k-i张，又由于最后被选中的攻击牌是第j张，所以所有合法情况下攻击牌的和之和，其实就是g_{j,k-i,0}。

而若要最终选出的k张牌是这k张牌，就剩余m-k张牌就需要满足：

因此方案数就是C_{n-j}^{m-k}。

总结一下，就是枚举i,j，然后每次答案加上f_{n,i,1}\cdot g_{j,k-i,0}\cdot C_{n-j}^{m-k}。

第二类：当m张强化牌中，强化牌的数量大于等于k-1时。

此时必然是选上权值最大的k-1张强化牌，然后选上权值最大的一张攻击牌。

对于这一种情况，我们枚举i,j分别表示最后被选中的强化牌是第i张和被选中的攻击牌是第j张。

在前i张强化牌中选择k-1张，且第i张必选，所有合法情况下的乘积之和，其实就是f_{i,k-1,0}。

选择第j张攻击牌，攻击牌之和其实就是第j张攻击牌的权值，也就是b_j。

而若要最终选出的k张牌是这k张牌，就剩余m-k张牌就需要满足：

因此方案数就是C_{2n-i-j}^{m-k}。

总结一下，就是枚举i,j，然后每次答案加上f_{i,k-1,0}\cdot b_j\cdot C_{2n-i-j}^{m-k}。

具体实现可见代码。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 6000
#define X 998244353
using namespace std;
int n,m,k,a[N+5],b[N+5],C[N+5][N+5],f[N+5][N+5][2],g[N+5][N+5][2];
I bool cmp(CI x,CI y) {return x>y;}
int main()
{
    RI i,j;for(C[0][0]=i=1;i<=N;++i) for(C[i][0]=j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%X;//预处理组合数
    RI Tt,ans;scanf("%d",&Tt);W(Tt--)
    {
        for(scanf("%d%d%d",&n,&m,&k),ans=0,i=1;i<=n;++i) scanf("%d",a+i);
        for(i=1;i<=n;++i) scanf("%d",b+i);sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);//从大到小排序
        for(f[0][0][0]=f[0][0][1]=i=1;i<=n;++i) for(f[i][0][1]=j=1;j<=i;++j)//预处理f
            f[i][j][0]=1LL*a[i]*f[i-1][j-1][1]%X,f[i][j][1]=(f[i][j][0]+f[i-1][j][1])%X;
        for(i=1;i<=n;++i) for(j=1;j<=i;++j)//预处理g
            g[i][j][0]=(1LL*b[i]*C[i-1][j-1]+g[i-1][j-1][1])%X,g[i][j][1]=(g[i][j][0]+g[i-1][j][1])%X;
        for(i=0;i<k-1;++i) for(j=1;j<=n;++j) ans=(1LL*f[n][i][1]*g[j][k-i][0]%X*C[n-j][m-k]+ans)%X;//当强化牌数量小于k-1时
        for(i=0;i<=n;++i) for(j=1;j<=n;++j) ans=(1LL*f[i][k-1][0]*b[j]%X*C[2*n-i-j][m-k]+ans)%X;//当强化拍数量大于等于k-1时
        printf("%d\n",ans);//输出答案
    }return 0;
}