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

Solution:

First, for each + operation, we only need count the number of subsequences which include this operation.

Let us assume the i-th operation is +, and the value of it is a[i]. If it be included by one of subsequence, then all the - operations in this process will not remove this a[i].
So that, for each - operation, it must be one of the two cases below:
1. It's j-th step, and j<i. For this case it will never remove a[i].
2. It's j-th step, and j>i. For this case, there at least be one value in the set which is smaller than a[i].

We define dp[j][k] to represent that: after j steps, there are k numbers in the set which is smaller than a[i]. Consider the step j can be applied or not applied. So, we have:  $$\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}
$$which means:
If step j is +, and the value is larger than a[i], then this operation will not affect k.
If step j is -, we get dp[j-1][k] possibilities for not apply this operation; and get dp[j-1][k+1] possibilities for apply this operation.
If step j is +, and the value is smaller than a[i], we get dp[j-1][k-1] possibilities if we apply this operation. Also, we can choose not to apply it.

Now, we get two special cases:

1. For a[j]=a[i]. Based on the QA for this problem. We can sort by index and remove the smaller one firstly.
2. For j<i and k=0 and a[j]=-1. Because the j is in front of i. So, it will not affect a[i] anyway. So, dp[j][0]=dp[j-1][0]+dp[j-1][0]+dp[j-1][k+1]. In another words, for k=0, it does not matter whether apply or not.

At the same time, we found that, we can compress the states. So, in the code, we just define dp[k] is enough for us.

Code:

Java

C++