1600: 赛车游戏

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t;
int dp[N];
int main(){scanf("%d",&t);while(t--){int n;scanf("%d",&n);vector<int> vec;vec.push_back(0);for(int i=1;i<=n;i++){int a;scanf("%d",&a);vec.push_back(a);}memset(dp,0x3f,sizeof(dp));dp[1]=0;bool flag=1;for(int i=1;i<=n;i++){if(dp[i]==0x3f3f3f3f)	{flag=0;break;}for(int j=1;j<=vec[i]&&i+j<=n;j++){if(dp[i]+1<dp[i+j]){dp[i+j]=dp[i]+1;//dp[i]存的是从1到i用了几辆车 }}}if(!flag){printf("-1\n");}else{if(n==1)printf("0\n");elseprintf("%d\n",dp[n]-1);	}}return 0;
}