数组染色

时间限制：1秒        内存限制：128M

题目描述

对于一个给定的数组a，小可要对其中的元素染色。染色规则如下：

第一个数字为a1​​ ，那么第一个数字和之后的 a​i​​ 个数字都被染成相同的颜色，然后第 a1+2a​1​​+2 个数字和它后面的 aa1+2 个数字都被染成第二种颜色……

这样的话，数组有很大的可能不能染色成功。所以我们可以删除若干个数字。请问最少删除多少个数字，使得数组可以染色成功。

例如：3 3 4 5 2 6 1 是可以直接成功染色的，a​1​​=3，a​1​​和它后面的3个数字染成一种颜色 ，之后a5=2，a​5​​和它后面的2个数字染成一种颜色。即3 3 4 5 染成一种颜色，2 6 1染成一种颜色。

例如： 1 8 5 5 2 6 1 ，不可以直接成功染色的，但是如果删a​3​​ 和 a​4​​ ，形成 1 8 2 6 1，就可以成功染色，1 8 染成一种颜色，2 6 1 染成一种颜色。

输入描述

第一行：输入一个正整数 t，表示多组测试的样例组数。

对于接下来 t 组数据：

第一行：输入一个正整数 n，表示数组包含多少个数字。

第二行：输入n个正整数，表示a数组。

输出描述

对于每组数据，输出一行一个正整数答案，表示最少删除多少个数字，剩下的数字可以成功染色。

输入样例

1. 7
2. 7
3. 3 3 4 5 2 6 1
4. 4
5. 5 6 3 2
6. 6
7. 3 4 1 6 7 7
8. 3
9. 1 4 3
10. 5
11. 1 2 3 4 5
12. 5
13. 1 2 3 1 2
14. 5
15. 4 5 5 1 5

输出样例

1. 0
2. 4
3. 1
4. 1
5. 2
6. 1
7. 0

数据描述

25%的数据下：1≤t,n,ai≤10

100%的数据下：1≤t≤10^4,1≤n≤2∗10^5,1≤ai≤10^6

数据保证，t 组数据的 n 的和，不超过2∗10^5

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 2*1e5+5;
long long n,a[N],T,x,q,dp[N],r[N];
int main(){scanf("%lld",&T);while(T--){scanf("%lld",&n);memset(dp,0x3f,sizeof dp);	dp[0]=0;for(int i=1;i<=n;i++){int x;cin>>x;dp[i]=min(dp[i-1]+1,dp[i]);if(i+x<=n)dp[i+x] = min(dp[i+x],dp[i-1]);}cout<<dp[n]<<"\n";}return 0;
}