CF1542D Priority Queue

就这伞兵题我居然赛场上写挂了。

首先一个简单的想法是分开考虑每一个 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]);

最后把方案数和当前数的值乘起来求和就可以了。

完整代码。

#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;
}