Mukhammadali and the Smooth Array

The important move is to stop obsessing over the changed values. They can be any integers, so they are basically programmable filler.

We only need to decide which original positions stay unchanged.

Key Observation

Suppose we keep some positions:

$i_1 < i_2 < \dots < i_k$

Since these positions are not changed, their final values are still:

$a_{i_1}, a_{i_2}, \dots, a_{i_k}$

The final whole array must be nondecreasing, so these kept values also must be nondecreasing:

$a_{i_1} \le a_{i_2} \le \dots \le a_{i_k}$

If you keep two positions $i < j$ with $a_i > a_j$, you're cooked. No amount of changing the stuff between them can make the array nondecreasing, because the left fixed value is already bigger than the right fixed value.

So the kept positions must form a nondecreasing subsequence of the original array.

Is that condition enough?

Yes.

If the kept values are nondecreasing, every changed position can be assigned some value that fits. Between two kept values $x \le y$, set all changed positions there to $x$ or $y$ or anything in between if you feel fancy. Before the first kept value, use something no larger than it. After the last kept value, use something no smaller than it.

Because equality is allowed, there is no annoying “not enough integers between them” problem. This is not one of those cursed strict-increasing traps.

So:

• changed positions cost money,
• unchanged positions save their change cost,
• unchanged positions must form a nondecreasing subsequence.

Therefore the problem becomes:

Find a nondecreasing subsequence with maximum total cost $c_i$.

Then subtract that saved cost from the total cost.

DP Definition

Let:

$dp[i] = \text{maximum saved cost of a nondecreasing subsequence ending at position } i$

If we keep position $i$, we save $c_i$.

Before $i$, we may append it after any position $j < i$ such that:

$a_j \le a_i$

So:

$dp[i] = c_i + \max_{j < i,\ a_j \le a_i} dp[j]$

If there is no such $j$, then:

$dp[i] = c_i$

The best saved cost is:

$best = \max_i dp[i]$

The answer is:

$\sum_{i=1}^{n} c_i - best$

For $n=1$, this naturally gives answer $0$, because we can keep the only element.

Complexity

The sum of $n$ over all test cases is at most $8000$, so the plain $O(n^2)$ DP is completely fine:

$O\left(\sum n^2\right)$

In the worst case that is around $64$ million transitions, which is chill for 1 second in C++ if you don't write it like a sleep-deprived spreadsheet.