PKUSC2018 Slay The Spire

有攻击牌和强化牌各 $n$ 张，强化牌可以让之后所有攻击牌攻击力乘一个大于 $1$ 的系数，攻击牌可以造成伤害

求所有“抽出 $m$ 张然后打 $k$ 张”能造成的伤害之和

$k,m,2n \leq 3000$

sol：

冷静一下，发现强化牌肯定要打完，因为一张攻击力最大的攻击牌就相当于没强化的强化牌

讨论一下抽到了几张强化牌

假设抽到了 $i$ 张强化牌，$k-i$ 张攻击牌

如果 $i < k$ 直接强化全打然后攻击就完事了，如果 $i \geq k$ 的话打最大的 $k-1$ 张强化和最大的一张攻击

由此可以 $dp$

设 $f_i$ 为 $i$ 张强化牌最多能扩的倍数，枚举当前抽到的强化牌 $j$，则

当 $i < k$ 时，$f_i = f_{i-1} + w_j \times f_j$

else, $f_i = f_i+f_{i-1}$

设 $g_i$ 为选了 $i$ 张攻击牌不翻倍的最大攻击力，枚举当前抽到的攻击牌 $j$，则

$g_i = g_{i-1} + C_{i-1}^{j-1} \times w_j + c$ (当 $i \leq (m-k+1)$ 时 $c=0$，$i>(m-k+1)$ 时 $c=g_{i-1}$)

答案就是 $\sum\limits_{i=0}^m f_i \times g_{m-i}$

第一个转移显然是按倍数从大到小排序，第二个需要把攻击力从小到大排序，

第一个转移，不管是怎么转移过来的，每张强化牌的贡献都是一样的，

第二个算每张牌贡献的时候，$c$ 标注了这张攻击牌打完之后还能不能再打别的攻击牌，如果不能打就是 $0$，能打的话要求跟他一起打的尽量大，这样转移能保证我们打的是一段尽量大的攻击牌

#include<bits/stdc++.h>

#define LL long long

#define rep(i,s,t) for(register int i = (s),i##end = (t); i <= i##end; ++i)

#define dwn(i,s,t) for(register int i = (s),i##end = (t); i >= i##end; --i)

using namespace std;

const int mod = ;

inline int read()

{

    int x=,f=;char ch;

    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f;

    for(;isdigit(ch);ch=getchar())x=*x+ch-'';

    return x*f;

}

bool cmp(int a, int b) { return a > b; }

LL fac[], inv[];

int T, n, m, k, ans, f[], g[], w[];

LL C(int n, int m) { return fac[n] * inv[m] % mod * inv[n - m] % mod; }

int main() {

    fac[] = fac[] = inv[] = inv[] = ;

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

        fac[i] = fac[i - ] * i % mod;

        inv[i] = ((LL)mod - mod / i) * inv[mod % i] % mod;

    }

    for (int i = ; i <= ; i++) inv[i] = inv[i] * inv[i - ] % mod;

    T = read();

    while (T--) {

        n = read(), m = read(), k = read();

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

        sort(w + , w + n + , cmp);

        for (int i = ; i <= max(n, m); i++) f[i] = ;

        f[] = ;

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

            for (int j = min(m, i); j >= ; j--)

                if (j <= k - )

                    f[j] = (f[j] + (LL)f[j - ] * w[i] % mod) % mod;

                else

                    f[j] = (f[j] + f[j - ]) % mod;

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

        sort(w + , w + n + );

        for (int i = ; i <= max(n, m); i++) g[i] = ;

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

            for (int j = min(m, i); j >= ; j--)

                if (j <= m - (k - ))

                    g[j] = (g[j] + (LL)C(i - , j - ) * w[i] % mod) % mod;

                else

                    g[j] = ((g[j] + g[j - ]) % mod + (LL)C(i - , j - ) * w[i] % mod) % mod;

        ans = ;

        for (int i = ; i <= m; i++) ans = (ans + (LL)f[i] * g[m - i] % mod) % mod;

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

    }

    return ;

}

当然比赛不会真的这么写...老老实实用两维状态前缀和优化，考后自然要选择好一点的写法

巴特西

PKUSC2018 Slay The Spire

最新文章

热门文章