CF1542D Priority Queue
Acfboy
2021-07-04 09:45:29
就这伞兵题我居然赛场上写挂了。
首先一个简单的想法是分开考虑每一个 $a_i$ 出现了多少次，因为考虑很多个数非常的困难，而只考虑一个数是否出现在最终的可重集中就方便得多了。
一个数出现在最后的充要条件是对于后面出现第 $k$ 个 `-` 时，都有至少 $k$ 个数比当前的数小。
那么就只需要考虑对于每一个数，满足以上充要条件的方案数有多少个就可以了。由于数据范围是 $500$, 所以求这个方案数的时间复杂度必须要在 $n^2$ 以内。
赛场上我想到 $f_i$ 表示到 $i$ 个 `-` 的合法方案有多少个，可是这样得枚举上一个转移来的位置 $j$, 但中间取多少个又不知道，还得枚举取了多少个。这样时间就变成了 $n^3$ 了，总时间复杂度 $n^4$, 无法通过。~~然后被一个错误的性质误导以为自己成功优化，最后噼里啪啦写完发现样例都过不了。~~
那么想想怎么优化这个 dp，我们真的需要关心两个 `-` 之间出现了多少个小于当前选的数的数吗？
其实不然，要知道的只是在出现 $x$ 个 `-` 后比当前小的是不是多于 $x$ 个。而且在背包问题中，并不需要枚举上一个选择的是哪里，只需要管当前这个取不取就可以了。
所以首先把状态改成 $f_{i,j}$ 表示取到 $i$，有 $j$ 个比当前选中的数小的方案数。然后模仿背包的时候，从前一个转移过来就可以了。
但实际上这个 $i$ 在处理到当前选的数之前的转移和之后的是不同的，因为之前的只需要选到 $j$ 个就行，而之后的必须保证满足上面的充要条件（不然当前这个就被仍了啊）。
具体地，选中枚举到的第 $i$ 个对于当前位置之前的转移:
- 若是 `+` 操作，那么 `add(f[j][k + (a[j] <= a[i])], f[j-1][k]);`。
- 对于 `-` 操作 `add(f[j][std::max(k-1, 0ll)], f[j-1][k]);`
（因为代码里枚举当前数用了 $i$ 所以这里只能用 $j,k$ 了）
而对于之后的转移：
- 若是 `+` 操作，那么 `add(f[j][k + (a[j] < a[i])], f[j-1][k])`。（有变化，`<=` 改 `<` 了，因为不能把这个给删了）
- 对于 `-` 操作 `if (k) add(f[j][k-1], f[j-1][k]);`（有变化，必须要满足条件才能加）
而若当前的不选，两边都是 `add(f[j][k], f[j-1][k]);`
最后把方案数和当前数的值乘起来求和就可以了。
完整代码。
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
const int N = 505, P = 998244353;
int n, a[N], x, f[N][N], ans;
char opt[5];
void add(int &x, int y) { x = (x + y) % P; }
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", opt);
if (opt[0] == '-') a[i] = -1;
else scanf("%lld", &x), a[i] = x;
}
for (int i = 1; i <= n; i++) {
if (a[i] == -1) continue;
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int j = 1; j < i; j++)
for (int k = 0; k <= j; k++) {
if (a[j] > 0) add(f[j][k + (a[j] <= a[i])], f[j-1][k]);
else add(f[j][std::max(k-1, 0ll)], f[j-1][k]);
add(f[j][k], f[j-1][k]);
}
for (int j = 0; j <= i; j++) f[i][j] = f[i-1][j];
for (int j = i+1; j <= n; j++)
for (int k = 0; k <= j; k++) {
if (a[j] > 0) add(f[j][k + (a[j] < a[i])], f[j-1][k]);
else if (k) add(f[j][k-1], f[j-1][k]);
add(f[j][k], f[j-1][k]);
}
for (int j = 0; j <= n; j++) add(ans, f[n][j] * a[i] % P);
}
printf("%lld", ans);
return 0;
}
```