很 AtCoder 的一道推性质题。
题目要求最后有多少种不同的情况，而这个东西正着考虑不好考虑，我们尝试以每种最终局面倒过来考虑是否合法。
那么第一个操作就从加任意一个数变成了删任意一个数，第二个操作从删最大值变成了加入一个最大值。这个最大值必须是最终局面中没有的数。
那么我们可以把没有选择的数看作一个空位。这个局面合不合法，就取决于每次第二个操作是否有一个空位大于当前的所有数。
那么我们肯定删数时贪心的删最大的数，而放数的时候一定尽可能放最小的。我们注意到，如果我们放了若干个数，那么我们删数时就必须先放的数然后才能接着删最终局面中的数。
那么我们就可以设计出一种贪心的方式：
先把 \(x_i\) 翻转，我们令当前剩余的空位有 \(x\) 个，第 \(k\) 个数后面的空位有 \(a_k\) 个，当前最大的没被删除的最终局面中的数为第 \(k\) 个，当前没有被删除的放入的数有 \(c\) 个。那么我们有以下流程：
- 如果 \(x_i=1\)，那么：
- 若 \(c=0\)，则令 \(x \gets a_k - a_{k - 1}, k \gets k - 1\)；
- 否则，令 \(c \gets c - 1\)；
- 如果 \(x_i=2\)，那么：
- 若 \(x \ge 1\)，那么令 \(x \gets x - 1, c \gets c + 1\)；
- 否则，该局面不合法。
我们发现，每一步时 \(c\) 的值是不受最终局面中的数的影响的，那么也就是说每一步时 \(x\) 的具体值是可以用最后局面中的数表示出来的。那么我们模拟以上过程，就能确定出每一个数后面的空位的最小值是多少。然后，我们就可以直接 DP 出有多少种空位的方案了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005, P = 998244353;
int f[MAXN][MAXN];
int a, b, x[2 * MAXN];
int g[MAXN];
int main() {
scanf("%d%d", &a, &b);
for (int i = 1; i <= a + b; i++) {
scanf("%d", &x[i]);
}
reverse(x + 1, x + 1 + a + b);
int c = 0, d = 1, k = a - b;
for (int i = 1; i <= a + b; i++) {
if (x[i] == 1) {
if (c) {
c--;
} else {
k--;
}
} else {
g[k] = max(g[k], d);
d++, c++;
}
}
for (int i = 0; i <= b; i++)
f[a - b + 1][i] = 1;
for (int i = a - b; i >= 1; i--) {
for (int j = g[i]; j <= b; j++) {
if (j) f[i][j] = f[i][j - 1];
f[i][j] = (f[i][j] + f[i + 1][j]) % P;
}
}
printf("%d\n", f[1][b]);
return 0;
}