Interesting Problem (Hard Version)
Contest: EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
Difficulty rating: 2600
Tags: dp

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if both versions of the problem are solved.

You are given an array of integers $$$a$$$ of length $$$n$$$.

In one operation, you will perform the following two-step process:

1. Choose an index $$$i$$$ such that $$$1 \le i < |a|$$$ and $$$a_i = i$$$.
2. Remove $$$a_i$$$ and $$$a_{i+1}$$$ from the array and concatenate the remaining parts.

Find the maximum number of times that you can perform the operation above.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 800$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$800$$$.

Output format:
For each test case, output a single integer — the maximum number of times that you can perform the operation.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one possible optimal sequence of operations is $$$[ 1, 5, \color{red}{3}, \color{red}{2}, 4 ] \rightarrow [\color{red}{1}, \color{red}{5}, 4] \rightarrow [4]$$$.

In the third test case, one possible optimal sequence of operations is $$$[1, \color{red}{2}, \color{red}{3}] \rightarrow [1]$$$.

Example input:
6
5
1 5 3 2 4
8
2 1 3 4 5 6 7 8
3
1 2 3
4
1 2 4 4
5
4 4 1 3 5
1
1

Example output:
2
3
1
2
0
0

Editorial:
Balanced bracket sequence analogy
Suppose there is a way to remove the entire array. Let's look at the process in reverse. Then, we are effectively inserting pairs of adjacent elements into an array until we get the original one. Let's look at a mirror process, where instead we keep inserting pairs of brackets $$$()$$$ to get a balanced bracket sequence.
For example, consider the array $$$[1, 2, 5, 4, 5, 7, 7, 1]$$$. Then, one possible way to delete it is $$$[1, 2, 5, 4, 5, 7, \color{red}{7}, \color{blue}{1}] \rightarrow [1, 2, 5, \color{red}{4}, \color{blue}{5}, 7] \rightarrow [1, \color{red}{2}, \color{blue}{5}, 7] \rightarrow [\color{red}{1}, \color{blue}{7}] \rightarrow []$$$. If we now build our bracket sequence, we get $$$\emptyset \rightarrow \color{red}{(}\color{blue}{)} \rightarrow (\color{red}{(}\color{blue}{)}) \rightarrow (()\color{red}{(}\color{blue}{)}) \rightarrow (()())\color{red}{(}\color{blue}{)}$$$.
Note that such a bracket sequence doesn't tell us in which order the operation needs to be performed, only on which indices.
Solution
Let's go back to the original problem. Suppose we want to eventually perform the operation on index $$$i$$$ (in the indexation of the original array). Then, two conditions must be met:
1. $$$a_i \equiv i \pmod{2}$$$ must hold, since the operation does not change the parity of indices.
2. Exactly $$$\frac{i - a_i}{2}$$$ operations must be made to the left of $$$a_i$$$ before we apply the operation on it.
This, together with the bracket analogy, leads to a pretty natural dynamic programming solution: $$$dp[l][r] = $$$ min number of operations that need to be performed to the left of $$$l$$$ to be able to remove the subsegment $$$a_l, \ldots, a_r$$$. If $$$l > r$$$, initialize $$$dp[l][r] := 0$$$, else initialize $$$dp[l][r] := +\infty$$$.
Similar to dps on balanced bracket sequences, for $$$a_l$$$, we will iterate over the other element $$$a_m$$$ with which we will perform the operation, $$$l \equiv m \pmod{2}$$$:
• If $$$dp[l+1][m-1]$$$ is greater than $$$\frac{l - a_l}{2}$$$, it is impossible to apply the operation on the pair $$$(a_l, a_m)$$$, so we do not update $$$dp[l][r]$$$.
• Else, it will take at least $$$op := \max(\frac{l - a_l}{2}, dp[m+1][r] - \frac{m-l+1}{2})$$$ operations to the left of $$$l$$$ to delete this subsegment if we want to perform the operation on $$$(a_l, a_m)$$$. So we update as follows: $$$dp[l][r] := \min(dp[l][r], op)$$$.
Suppose we have calculated all the values of $$$dp[l][r]$$$. Let's introduce $$$dp2[r] =$$$ the maximum number of times that we can perform the operation on the prefix $$$a_1, a_2, \ldots, a_r$$$, initially $$$dp2[r] := 0$$$ for all $$$0 \le r \le n$$$. Then, for some $$$r$$$, the transitions are to iterate over all $$$1 \le l \le r$$$ and update $$$dp2[r] := \max(dp2[r], dp2[l - 1] + \frac{r - l + 1}{2})$$$ if $$$dp[l][r] \le dp2[l - 1]$$$ holds.
The answer to the problem is $$$dp2[n]$$$.
It takes $$$\mathcal{O}(n^3)$$$ time to calculate the values of $$$dp[l][r]$$$, and $$$\mathcal{O}(n^2)$$$ time for $$$dp2[r]$$$.
Complexity: $$$\mathcal{O}(n^3)$$$
Note: to solve F1, you can calculate the values of $$$dp[l][r][k] =$$$ the maximum number of operations that you can perform on the subsegment $$$a_l, \ldots, a_r$$$ if exactly $$$k$$$ operations were performed to the left of $$$l$$$, which can be done similar to the way above in $$$O(n^4)$$$. The answer will be $$$dp[1][n][0]$$$.