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

Author Avatar
ZigZagK 2018年5月17日 17:06
remove_red_eye 479

题目概述

\(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)\) 同理。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3000,MOD=998244353;

int te,n,m,K,a[maxn+5],b[maxn+5],C[maxn+5][maxn+5];
int f[maxn+5][maxn+5],g[maxn+5][maxn+5],sum[maxn+5],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    for (int i=C[0][0]=1;i<=n;C[i++][0]=1)
        for (int j=1;j<=i;j++) AMOD(C[i][j]=C[i-1][j-1],C[i-1][j]);
}
#define C(x,y) ((x)<(y)?0:C[x][y])
inline bool cmp(const int &A,const int &B) {return A>B;}
inline int F(int x,int y){
    int ans=0;
    for (int i=y;i<=n;i++)
        AMOD(ans,(LL)C(n-i,x-y)*f[i][y]%MOD);
    return ans;
}
inline int G(int x,int y){
    int ans=0;
    for (int i=y;i<=n;i++)
        AMOD(ans,(LL)C(n-i,x-y)*g[i][y]%MOD);
    return ans;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (Make(maxn),scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&K);
        for (int i=1;i<=n;i++) scanf("%d",&b[i]);sort(b+1,b+1+n,cmp);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n,cmp);
        memset(sum,0,sizeof(sum));
        for (int i=1;i<=n;i++)
            for (int j=i;j;AMOD(sum[j],f[i][j]),j--)
                AMOD(f[i][j]=sum[j-1],(LL)C(i-1,j-1)*a[i]%MOD);
        memset(sum,0,sizeof(sum));g[0][0]=sum[0]=1;
        for (int i=1;i<=n;i++)
            for (int j=i;j;AMOD(sum[j],g[i][j]),j--)
                    g[i][j]=(LL)sum[j-1]*b[i]%MOD;
        for (int i=0;i<m;i++)
            if (i>K-1) AMOD(ans,(LL)F(m-i,1)*G(i,K-1)%MOD);
            else AMOD(ans,(LL)F(m-i,K-i)*G(i,i)%MOD);
        printf("%d\n",ans);ans=0;
    }
    return 0;
}

本文链接:https://zigzagk.top/2018/05/17/loj2538
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。