[ARC127E] Priority Queue 题解

首先我们每次加入的数必定是一个 \(1\sim a\) 的排列，但从排列角度考虑的话非常复杂，因为 \(s\) 是一个集合。所以我们考虑最后能剩下哪些数。

考虑最后剩下的集合为 \(\{a_i\}\)，其中 \(a_i<a_{i+1}\)，显然这个集合里面的元素个数为 \(A-B\)。

那么我们会发现一件事情：我们按上升序依次留下这些数是最优的。

考虑相邻两个数 \(a_i,a_{i+1}\)，若以 \(a_{i+1},a_i\) 的顺序可以留下这些数，那么：

• 由于 \(a_{i+1}>a_i\)，将 \(a_i\) 调到 \(a_{i+1}\) 的位置必定更容易被留下。
• 由于 \(a_{i+1}\) 出现在 \(a_i\) 前面，因此若 \(a_{i+1}\) 在前面可以被留下，那么放到 \(a_i\) 的位置也必定可以留下。

于是我们最后留下的数必定是有序的，所以我们如果已经确定了前 \(i\) 个数，第 \(i+1\) 个数的下界就对应的被确定了（\(a_i<a_{i+1}\)）。因为在一个位置填上小一点的数必定比大一点的数更容易留下，所以 \(a_{i+1}\) 的值域是一段连续的区间，我们只需要知道上界即可。

考虑贪心，我们为了让每一位上的数尽可能的大，肯定要让大的数尽量留在后面，所以按从小到大的顺序依次加数即可。

最后就是一个简单 dp 了。

#include <atcoder/all>
#include <iostream>

using namespace std;
using LL = atcoder::modint998244353;

const int kN = 5001;

int a, b, r[kN], t;
LL f[kN][kN], s[kN][kN];

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> a >> b;
  for (int i = 1, v, j = 0; i <= a + b; ++i) {
    cin >> v;
    if (v == 1) {
      r[++t] = ++j;
    } else {
      --t;
    }
  }
  f[0][0] = 1;
  for (int i = 0; i <= a; ++i) {
    s[0][i] = 1;
  }
  for (int i = 1; i <= a - b; ++i) {
    for (int j = 1; j <= r[i]; ++j) {
      f[i][j] = s[i - 1][j - 1];
      s[i][j] = s[i][j - 1] + f[i][j];
    }
    for (int j = r[i] + 1; j <= a; ++j) {
      s[i][j] = s[i][r[i]];
    }
  }
  cout << s[a - b][r[a - b]].val();
  return 0;
}