题解|#E. Sending a Sequence Over the Network# cf round 826

这个题的原问题是，从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;
}