题目描述
难度分:1500
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105)和长为n的数组a(1≤a[i]≤106)。
对于数组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]可以删或者不删:
- 如果删,状态转移方程为f[i]=1+f[i+1];
- 如果不删,状态转移方程为f[i]=f[i+a[i]+1],表示[i,i+a[i]]属于一个块,i+a[i]+1是下一个块的起点。
两者选较小的转移。利用记忆化搜索来实现这个DP
,如果i>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;
}