CF2232C1题解

传送门：https://www.luogu.com.cn/problem/CF2232C1

假如我们确定下坐下的 \(I\) 类人的数目，我们可以为 \(E\) 类人执行以下贪心策略：保证在有足够位置给确定下的 \(I\) 类人前提下，尽量占用更多的桌子为 \(E\) 类人提供尽量大的空间。

我们枚举坐下的 \(I\) 类人的数目，维护当前坐到的桌子编号和剩余的留给 \(E\) 类人座位数即可。时间复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>const int N = 5e5 + 1;using namespace std;char a[3002];void solve() {int n, x, s;cin >> n >> x >> s;cin >> a + 1;int res = 0;for (int k = 0; k <= x; ++k) {int c = k, ans = 0, v = 0, now = 0;for (int i = 1; i <= n; ++i) {if (a[i] == 'A') {if (x - now > c) {++now;v += s - 1;++ans;} else {if (v) {--v;++ans;}}} else if (a[i] == 'I') {if (c) {--c;++now;v += s - 1;++ans;}} else {if (v) {--v;++ans;}}}res = max(res, ans);}cout << res << '\n';
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}