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]。

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

  1. 对于a[j]=a[i]的情况。这种情况根据这道题的QA,我们可以以i和j的大小来区分,下标小的先删除即可。
  2. 对于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

Submission #121300356 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #121304276 - Codeforces
Codeforces. Programming competitions and contests, programming community