[ABC238F] Two Exams 题解

2020luke · 2024-02-29 22:45:15 · 题解

[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。

时间复杂度：第一维枚举每一个人，第二维枚举选几个人，第三维枚举当前最小值，因此为 O(mn^{2})。

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) { //判断，不能使当前人的排名落后于 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;
}