这个题的原问题是,从1n有没有一个正确的序列划分,可以缩小为子问题,从1i有没有正确的序列划分,由于子问题和原问题的求解方式一样,且原问题需要由子问题推来,这就说明了这个题需要用动态规划来求解(不过蒟蒻一开始也没想到动态规划,还是太菜了)。

考虑递推方程怎么写,由于只用判断整体区间划分能否正确,所以设一个一维bool数组即可,

bool f[i] 代表着以第i个位置为结尾的子区间能否被正确划分

递推的过程需要分类讨论,因为i可以是结尾,也可以是起始

1、当i为结尾时,那么就判断前i-a[i]-1长度的区间能否被正确划分,如果可以,那么前i长度的区间也能被正确划分,bool数组置true;

2、当i为起始时,要判断会不会越界,然后如果前i-1长度的区间能被正确划分,那么前**i+a[i]**长度的区间也能被正确划分

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
typedef long long ll;
int b[M];
bool f[M]; 
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		for(int i=1;i<=n;i++){
			cin>>b[i];
			f[i]=false;
		}
	//	for(int i=1;i<=n;i++) cout<<b[i]<<" ";
	//	cout<<endl;
		f[0]=true;
		for(int i=1;i<=n;i++){
			if(i>b[i]){
				if(f[i-b[i]-1]) f[i]=true;
			}
			if((b[i]+i)<=n&&f[i-1]){
				f[i+b[i]]=true;
			}
		}
	//	for(int i=1;i<=n;i++) cout<<f[i]<<" ";
	//	cout<<endl;
		if(f[n]) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}