题目描述

难度分:$1800$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你可以执行如下操作任意次：

• 选择$a$的一个非空连续子数组，把其中的元素都乘上整数$x$（注意$x$可以是负数）。

问：把$a$变成严格递增数组，最少需要操作多少次？

输入样例

3
5
1 1 2 2 2
6
5 4 3 2 5 1
3
1 2 3

输出样例

3
2
0

算法

思维题+线性DP

比较容易发现的一点就是负数肯定是用在一个严格降序的子数组上，因为严格降序的子数组只要乘上一个负数就会变为严格升序，但是什么时候用乘负数的操作不好说。

这个地方大胆猜测了一下，肯定会存在一个最优解，使得把整个数组变为严格递增的最后一步是将严格降序的前缀乘以一个负数翻转，拼接上严格升序的后缀使得整个数组有序，然后我们可以枚举这个分割点。先进行一遍动态规划：

状态定义

$f[i]$表示只使用乘以正数的操作将后缀$[i,n]$变为严格升序的最少操作次数。

状态转移

倒序遍历数组$a$

1. 如果发现$a[i] \geq a[i+1]$，由于后缀$[i+1,n]$已经严格升序了，那就可以通过对后缀$[i+1,n]$乘以一个正数将整体拉上去使$a[i] \lt a[i+1]$成立，从而使得后缀$[i,n]$严格升序，此时状态转移方程为$f[i]=f[i+1]+1$。
2. 如果$a[i] \lt a[i+1]$，那后缀$[i,n]$本来就是严格升序的，此时状态转移方程为$f[i]=f[i+1]$。

做完上述的动态规划之后，再正序遍历$a$，考虑将前缀变为严格降序，方式和“将后缀变为严格升序”是一样的，一旦发现$a[i-1] \leq a[i]$，那$a[i]$就要乘以一个负数使$a[i-1] \gt a[i]$成立。如果以$i$位置为分割点（即升序的最后一个元素），那么答案就是$g[i]+f[i+1]+1$，维护所有$i$的答案最小值即可（其中$g[i]$是将前缀$[1,i]$变为降序的最少操作次数，加$1$是对前缀$[1,i]$乘以一个负数，使严格降序变为严格升序，进一步让整个数组变为严格升序）。

这里不用考虑$a[i]$和$a[i+1]$在操作后不满足$a[i] \lt a[i+1]$，因为只是强调后缀$[i+1,n]$是严格升序，并没有强调它的绝对大小，事实上由于可以乘的$x$是任意的，一定存在能使$a[i]$和$a[i+1]$操作后能够接起来的$x$。

复杂度分析

时间复杂度

遍历了两遍数组$a$，时间复杂度为$O(n)$。

空间复杂度

空间开销的瓶颈在于DP数组$f$，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010, INF = 0x3f3f3f3f;
int t, n, a[N], f[N];

int solve() {
    f[n] = 0;
    for(int i = n - 1; i >= 1; i--) {
        f[i] = f[i + 1] + (a[i] >= a[i + 1]? 1: 0);
    }
    int ans = f[1], res = 0;
    for(int i = 2; i <= n; i++) {
        if(a[i] >= a[i - 1]) res++;
        ans = min(ans, 1 + res + f[i + 1]);
    }
    return ans;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        printf("%d\n", solve());
    }
    return 0;
}