8148: USACO 2022 January Contest, Platinum Problem 2. Counting Haybales
[Creator : ]
Description
As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has N (1≤N≤5000) stacks of haybales. For each i∈[1,N], the i-th stack has $h_i\ (1≤h_i≤10^9)$ haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
- If two adjacent stacks' heights differ by exactly one, she can move the top haybale of the taller stack to the shorter stack.
Input
The first line contains T (1≤T≤10), the number of independent test cases, all of which must be solved to solve one input correctly.
Each test case consists of N.
Then a sequence of N heights. It is guaranteed that the sum of N over all test cases does not exceed 5000.
Then a sequence of N heights. It is guaranteed that the sum of N over all test cases does not exceed 5000.
Output
Please output T lines, one for each test case.
Sample 1 Input
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5
Sample 1 Output
4
4
5
15
9
8
19
For the first test case, the four possible configurations are:
(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2).
For the second test case, the four possible configurations are:
(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2).