LOJ #2538. 「PKUWC2018」Slay the Spire

题目地址：[大家好，我是"题目地址"](https://loj.ac/problem/2538)

想比较不容易偏，但写着细节贼多的题。
首先考虑最优策略，注意到题目给出强化牌的$wi>1$的条件。
因此，优先打出最大的强化牌一定是最优的，考虑选择了两张最大的攻击牌，仍然与选择最小的强化牌等价。

接下来我们考虑选牌的情况：
设拿到了强化牌$c$张，攻击牌$m-c$张。
1、$c\ge k$ 策略是选出前$k-1$大的强化牌，选出最大的攻击牌。
2、$c<k$ 策略是选出全部$c$张强化牌，并选出前$k-c$大的攻击牌。

那么我们预处理，设$f(i,j)$表示拿出$i$张攻击卡，选择前$j$大进行攻击的所有方案得分和。
设$g(i,j)$表示拿出$i$张强化卡，选择前$j$大进行强化的所有方案得分和。

这个东西并不是很好预处理，直接$dp$复杂度有问题。
考虑组合计数的一个小操作：
我们先将两种牌分别排序，这样我们可以$dp$在前$i$大中选了$j$个的方案，这个是$O(n^2)$的。
这样我们访问$f(i,k)$就定死了前$k$大分别是什么。
设总共有$n$张牌，要选出$m$张，前$k$大的贡献和，
那么我们再在剩下的$n-i$个里选出$m-i$个就行了。
这个统计是$O(n)$的，由于我们只查询$n$次，
总复杂度$O(n^2)$。

p.s.小心，细节很多

```
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#define LL long long
using namespace std;
const int maxn = 3e3 + 5;
const int mod = 998244353;
LL step[maxn], inv[maxn];
int n, m, k, a[maxn], b[maxn];
LL f[maxn][maxn], g[maxn][maxn], s[maxn], ans;

void Add(LL &x, const LL &a) {
	x += a; if(x >= mod) x -= mod;
}

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

void pre(int n) {
	inv[0] = step[0] = 1;
	for(register int i = 1; i <= n; ++i) step[i] = step[i - 1] * i % mod;
	inv[n] = fpow(step[n], mod - 2);
	for(register int i = n - 1; i >= 1; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}

LL C(int n, int m) {
	if(n < m) return 0;
	return (step[n] * inv[n - m] % mod) * inv[m] % mod;
}

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

//摸x张牌，取最大k张 
LL GetF(int x, int k) {
	LL ans = 0;
	for(register int i = k; i <= n; ++i)
		Add(ans, C(n - i, x - k) * f[i][k] % mod);
	return ans;
}

//摸x张牌，取最大k张 
LL GetG(int x, int k) {
	LL ans = 0;
	for(register int i = k; i <= n; ++i)
		Add(ans, g[i][k] * C(n - i, x - k) % mod);
	return ans;
}

int main() {
	int t;
	scanf("%d", &t);
	pre(3000);
	while(t--) {
		ans = 0;
		scanf("%d%d%d", &n, &m, &k);
		for(register int i = 1; i <= n; ++i)
			scanf("%d", &b[i]);
		for(register int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		sort(a + 1, a + n + 1, cmp);
		sort(b + 1, b + n + 1, cmp);
		memset(s, 0, sizeof(s));
		for(register int i = 1; i <= n; ++i) {
			for(register int j = 1; j <= k; ++j)
				f[i][j] = (s[j - 1] + C(i - 1, j - 1) * a[i] % mod) % mod;
			for(register int j = 1; j <= k; ++j)
				Add(s[j], f[i][j]);
		}
		memset(s, 0, sizeof(s));
		g[0][0] = 1, s[0] = 1;
		for(register int i = 1; i <= n; ++i) {
			for(register int j = 1; j <= k; ++j)
				g[i][j] = (1ll * s[j - 1] * b[i]) % mod;
			for(register int j = 1; j <= k; ++j)
				Add(s[j], g[i][j]);
		}
		for(register int i = max(m - n, 0); i <= min(m - 1, n); ++i) {
			if(i < k) {
				Add(ans, GetG(i, i) * GetF(m - i, k - i) % mod);
				//cout << GetG(i, i) << " " << GetF(m - i, k - i) << endl;
			}
			else {
				Add(ans, GetG(i, k - 1) * GetF(m - i, 1) % mod);
				//cout << GetG(i, k - 1) << " " << GetF(m - i, 1) << endl;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链