[ABC238F] Two Exams 题解

思路解析

这题很麻烦，因为有两个维度。所以可以想到先按照第一维排序，这样就不需要考虑第二维的问题。其次再发现数据范围小，可以想到能用 dp 做，接下来就考虑如何 dp。首先我们要知道我们遍历到了第几个公民，同时还要知道还剩下几个代表名额，同时我们还需要思考第二维对选择代表的影响。于是想到 \(f_{i,j,k}\) 表示考虑完了前 \(i\) 个人，选了 \(j\) 个公民做代表，在没有被选为代表的人中第二维的值最小的值是 \(k\)。原因是我们已经按照第一位排好了序，当前的人在第一维上的排名一定落后于第二维是 \(k\) 的人，如果当前人在第二维上依然落后于 \(k\)，就必定不可以选。

然后考虑状态转移，分为选和不选两种情况。

• 如果不选，\(j\) 不变，但需要更新 \(k\)，所以可得 \(f_{i,j,\min(k,q_{i})} \gets f_{i-1,j,k}\)

• 如果选，则 \(j\) 需要加一，同时比较 \(q_{i}\) 和 \(k\)，可得 \(f_{i,j,k} \gets f_{i-1,j-1,k}\)

最后的答案就是 \(\sum_{i=1}^{n+1}f_{n,m,i}\)。

细节：初始时没有一个人不选，\(k\) 为 \(n+1\)，以及统计答案时也有可能没有一个人不选，记得遍历到 \(n+1\)。

code

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define fir first
#define sec second
const int N = 310, mod = 998244353;
int n, m, f[N][N][N];
PII a[N];
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].fir; 
	}
	for(int i = 1; i <= n; i++) {
		cin >> a[i].sec;
	}
	sort(a + 1, a + n + 1, [](PII x, PII y) { return x.fir < y.fir;});
	f[0][0][n + 1] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= m; j++) {
			for(int k = 1; k <= n + 1; k++) {
				f[i][j][min(a[i].sec, k)] = (f[i][j][min(a[i].sec, k)] + f[i - 1][j][k]) % mod;
				if(j > 0 && a[i].sec < k) {
					f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k]) % mod;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n + 1; i++) ans = (ans + f[n][m][i]) % mod;
	cout << ans;
	return 0;
}