F – Two Exams

题目描述：

n个考生，参加了两次考试，第一次的排名是Pi，第二次是Qi,现在需要选m名考生去参加活动，必须保证不能存在未被挑中的人x的第一次的和第二次的排名比选中的人y的第一次和第二次的排名都靠前，也就是不可以出现如下的情况$p[x]<p[y]且q[x]<q[y],x为被选中，y被选中$，问有多少种挑选方法，模 998244353

思路：

第一眼看见p[x]<p[y],q[x]<q[y]以为是二维偏序统计答案的题，但是后来发现是求k个人，且是不能出现(x, y)满足那个条件，就不是那种二维偏序，但是可以从二维偏序的角度来考虑

将第一维进行排序，保证p[x]<p[y],得到一个rk[i]数组，再进行dp

dp[i][j][k]表示前i个人中挑了j个人，且前i个中未被选中的人的第二维最小值是k的方案数量

对于每个i，有两种决策

• 选i,当j < m && rk[i] < k，即还可以选人，且当前人的排名要小于前面没被选中的人的排名的最小值
• 不选i

对应的两种决策的转移方程是：

• dp[i][j + 1][k] += dp[i - 1][j][k]
• dp[i][j][min(rk[i], k)] += dp[i - 1][j][k]

初始值是dp[0][0][n + 1] = 1

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int ar[MAX], br[MAX], rk[MAX];
int dp[305][305][305];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i];
    }
    for(int i = 1; i <= n; ++i){
        cin >> br[i];
        rk[ar[i]] = br[i];
    }
    dp[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){
                if(rk[i] < k && j < m){
                    (dp[i][j + 1][k] += dp[i - 1][j][k]) %= mod;
                }
                (dp[i][j][min(rk[i], k)] += dp[i - 1][j][k]) %= mod;
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n + 1; ++i){
        (ans += dp[n][m][i]) %= mod;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}