loj2538 「PKUWC2018」Slay the Spire

题目传送门

传送门


分析

首先有个结论:若抽出的牌中强化牌$\ge k-1$张,最优策略一定是出$k-1$张最大的强化牌,然后出一张最大的攻击牌。若强化牌不足$k-1$张,则最优策略为先打完所有强化牌,剩下打最大的几张攻击牌。

枚举抽了几张强化牌,几张攻击牌。设$f_i$表示抽$i$张攻击牌所有方案的强化倍数之和,$g_i$表示抽$i$张攻击牌所有方案的攻击力之和,则答案为$\sum_{i=0}^{n}f(i)\cdot g(m-i)$。

对于$f$,把强化牌降序排序,设当前做到第$j$张牌,

$$f_i = \begin{cases} f_i + f_{i - 1}\cdot a[j] & i < k\ f_i + f_{i - 1} & i \ge k \end{cases}$$

这样可以保证只打最大的几张牌,并且不会打超过$k-1$张。

对于$g$,思路相似。把攻击牌升序排序,设当前做到第$j$张牌,

$$ g_i = g_i + C(i-1,j-1)\cdot a[j] + \begin{cases} 0 &i\le m - (k - 1)\ g_{i - 1} & i>m - (k - 1) \end{cases} $$

这样可以保证牌少时打最大的一张,牌多时打最大的几张。

复杂度$O(n^2)$。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 3e3+50;
const int P = 998244353;

int n, m, k;
int a[N], b[N];
int f[N], g[N];
int c[N][N];

void add(int &x, int y) {
    x += y;
    if (x >= P) x -= P;
    if (x <= -P) x += P;
}

void initC() {
    for (int i = 0; i < N; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++)
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % P;
    }
}

int C(int x, int y) {
    return c[x][y];
}

void solve() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    std::sort(a+1, a+n+1, std::greater<int>());
    std::sort(b+1, b+n+1);
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    f[0] = 1;
    for (int j = 1; j <= n; j++) {
        for (int i = std::min(j, m); i >= 1; i--) {
            if (i < k) add(f[i], (ll)f[i-1] * a[j] % P);
            else add(f[i], f[i-1]);
        }
    }
    for (int j = 1; j <= n; j++) {
        for (int i = std::min(j, m); i >= 1; i--) {
            add(g[i], (ll)b[j] * C(j-1, i-1) % P);
            if (i > m - (k-1)) add(g[i], g[i-1]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= m; i++)
        add(ans, (ll)f[i] * g[m-i] % P);
    printf("%d\n", ans);
}

int main() {
    initC();
    int T;
    scanf("%d", &T);
    while (T--) solve(); 
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论