题目描述

难度分:$1500$

输入$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^6)$。

对于数组$B$，如果其满足$B[0]+1=len(B)$，那么称数组$B$为「块」。

对于数组$A$，如果可以将其划分成若干个「块」，那么称数组$A$是合法的。

例如$A=[3,3,4,5,2,6,1]$是合法的，因为$A=[3,3,4,5]+[2,6,1]$，这两段都是块。

把数组$a$变成合法数组，至少要删除多少个元素？

输入样例

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

输出样例

0
4
1
1
2
1
0

算法

动态规划

状态定义

$f[i]$表示将数组$[i,n]$合法化最少需要删除的元素个数，在这个定义下答案就是$f[1]$。

状态转移

当前元素$a[i]$可以删或者不删：

1. 如果删，状态转移方程为$f[i]=1+f[i+1]$；
2. 如果不删，状态转移方程为$f[i]=f[i+a[i]+1]$，表示$[i,i+a[i]]$属于一个块，$i+a[i]+1$是下一个块的起点。

两者选较小的转移。利用记忆化搜索来实现这个DP，如果$i \gt n$，则$i=n+1$时才是完整地划分完了整个数组$a$，返回$0$；否则最后一个块的长度是不合法的，返回一个大数（$n$就可以了，就当把整个数组都删了）。

复杂度分析

时间复杂度

状态个数是$O(n)$级别，单次转移的时间复杂度为$O(1)$，所以整个算法的时间复杂度为$O(n)$。

空间复杂度

空间消耗就是DP数组$f$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, a[N], f[N];

int dfs(int i) {
    if(i > n) return i == n + 1? 0: n;
    int &v = f[i];
    if(v != -1) return v;
    return v = min(1 + dfs(i + 1), dfs(i + 1 + a[i]));
}

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