Codeforces Round #729 Priority Queue 题解 (Java/C++)

题解

立刻可以想到，我们只需要统计每个+操作的x能在多少种子序列中出现即可。

假设第i步是+操作，其值为a[i]。如果这个a[i]保留到最后，那么整个过程中的所有-操作都不会操作到a[i]。也就是说，这个整个过程中，执行-操作时，必为下面两种情况之一：
1. 当前是第j步操作且j<i。这种情况无论如何都删不到a[i]。
2. 当前是第j步操作且j>i。集合中至少有一个数的值小于a[i]。

于是我们定义dp[j][k]表示，经过了j步后，集合中有k个小于a[i]的数的所有可能。考虑第j步可以选择执行或者不执行，于是有$$\begin{cases}
dp[j][k]=dp[j-1][k]+dp[j-1][k], &(a[j]>a[i])\\
dp[j][k]=dp[j-1][k]+dp[j-1][k+1], &(a[j]=-1)\\
dp[j][k]=dp[j-1][k]+dp[j-1][k-1], &(a[j]<a[i])\\
\end{cases}
$$也就是说：
如果j是+操作，且值大于a[i]，那么这个操作执不执行都不影响小于k的数目。
如果j是-操作，那么要么不执行，也就是dp[j-1][k]；要么执行，那么其可能数为dp[j-1][k+1]。
如果j是+操作，且值小于a[i]，要么不执行，要么就能增加一个小于a[i]的数，也就是dp[j-1][k-1]。

现在这里有几个特殊情况：

对于a[j]=a[i]的情况。这种情况根据这道题的QA，我们可以以i和j的大小来区分，下标小的先删除即可。
对于j<i且k=0且a[j]=-1的情况。这种情况比较特殊，因为j在i前面，无论如何都不会影响到a[i]，因此dp[j][0]=dp[j-1][0]+dp[j-1][0]+dp[j-1][k+1]。也就是说，如果原来的k=0，执不执行都可以。

同时，这里我们可以注意到的是，这里显然是可以状态压缩的。因此代码中直接定义dp[k]即可。

代码

Java

C++