BZOJ5467 PKUWC2018Slay the Spire（动态规划）

　　即求所有情况的最大伤害之和。容易发现应该先打强化牌，至少打一张攻击牌。同样显然的是强化牌和攻击牌都应该按从大到小的顺序打。进一步可以发现，只要还有强化牌，就应该使用（当然至少留一次攻击的机会）。

　　于是将强化牌和攻击牌各自从大到小排序。显然可以将其分开考虑。对强化牌，设f[i][j]为前i张牌抽到j张并打出的强化倍数之和，则显然有f[i][j]=f[i-1][j]+f[i-1][j-1]·w[i]。这样就搞定了强化牌可以打完的情况。同时设g[i]为抽i张打出k-1张的强化倍数之和，dp过程中通过f数组计算，注意避免重复。对于攻击牌也进行类似dp。然后枚举两种牌各抽了几张合并一下答案即可。注意细节。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 3010

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,n,m,k,a[N],b[N],f[][N][N],g[][N],C[N][N],h[N];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5467.in","r",stdin);

    freopen("bzoj5467.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    while (T--)

    {

        n=read(),m=read(),k=read();int lim=min(k-,n);

        C[][]=;

        for (int i=;i<=n;i++)

        {

            C[i][]=C[i][i]=;

            for (int j=;j<n;j++)

            C[i][j]=(C[i-][j-]+C[i-][j])%P;

        }

        memset(f,,sizeof(f));memset(g,,sizeof(g));memset(h,,sizeof(h));

        for (int i=;i<=n;i++) a[i]=read();

        for (int i=;i<=n;i++) b[i]=read();

        sort(a+,a+n+),reverse(a+,a+n+);

        sort(b+,b+n+),reverse(b+,b+n+);

        f[][][]=;

        for (int i=;i<=n;i++)

        {

            f[][i][]=;

            for (int j=;j<=lim;j++)

            f[][i][j]=(f[][i-][j]+1ll*f[][i-][j-]*a[i])%P;

            if (lim==) for (int j=;j<=n;j++) g[][j]=C[n][j];

            else

            for (int j=lim;j<=n;j++)

            g[][j]=(g[][j]+1ll*f[][i-][lim-]*a[i]%P*C[n-i][j-lim])%P;

        }

        for (int i=;i<=n;i++)

        {

            for (int j=;j<=m;j++)

            f[][i][j]=(f[][i-][j]+f[][i-][j-]+1ll*b[i]*C[i-][j-])%P;

            for (int j=m-k+;j<=n;j++)

            g[][j]=(g[][j]+(f[][i-][j-(m-k)-]+1ll*b[i]*C[i-][j-(m-k)-])%P*C[n-i][m-k])%P;

        }

        for (int i=;i<=min(n,m);i++)

            for (int j=;j<=n;j++)

            h[i]=(h[i]+1ll*b[j]*C[n-j][i-])%P;

        /*for (int i=0;i<=n;i++) cout<<f[0][n][i]<<' ';cout<<endl;

        for (int i=0;i<=n;i++) cout<<g[0][i]<<' ';cout<<endl;

        for (int i=0;i<=n;i++) cout<<f[1][n][i]<<' ';cout<<endl;

        for (int i=0;i<=n;i++) cout<<g[1][i]<<' ';cout<<endl;

        for (int i=0;i<=n;i++) cout<<h[i]<<' ';cout<<endl;*/

        int ans=;

        for (int i=max(,m-n);i<=min(n,m);i++)

        if (i<=lim) ans=(ans+1ll*f[][n][i]*g[][m-i])%P;//抽了i张强化牌 全部出完 剩余m-i张攻击牌 选m-k张不出

        else ans=(ans+1ll*g[][i]*h[m-i])%P;//抽了i张强化牌 选lim张出 剩余m-i张攻击牌 出1张

        printf("%d\n",ans);

    }

    return ;

}
 

BZOJ5467 PKUWC2018Slay the Spire（动态规划）的相关教程结束。