Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
by yejinru
/*
其实这题是我们通化区域邀请赛的C题提取出的一个子问题,这次把他当做一个比较简单的题目来出。
分析:
a[i]>=k;
a[i+1]>=k-1;
a[i+k-2]>=2;
a[i+k-1]>=1;
我们可以从后往前倒推。假设以当前位置为起点(不妨假设为位置i)最大符合题意的连续子串长度为len,
即表示a[i]>=len,a[i+1]>=len-1,...a[i+len-1]>=1 (假设)刚开始len = 0。
1.如果当前项a[i]>len,根据假设,可以把a[i]直接加到连续子串的第一位,len++
2.如果当前项a[i]<=len,根据假设,后面的数我们可以发现是不用考虑了的,这时只需要把a[i]放进
子串的第一位,因为需要满足a[i]>=a[i],(a[i+1]>=a[i]-1...a[i+a[i-1]-1]>=1)这显然满足,
所以把a[i]放进来的时候,len = a[i]。
每一步更新答案。
没看明白的话,大家自己想一下应该就能够想明白的。
*/
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define debug puts("here")
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)
#define pb push_back
#define RD(n) scanf("%d",&n)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
/******** program ********************/
const int MAXN = 1e5+5;
int a[MAXN],n;
void solve(){
RD(n);
rep(i,n)
RD(a[i]);
int len = 0;
int ans = 0;
for(int i=n-1;i>=0;i--){
if(len<a[i])
len ++;
else
len = a[i];
ans = max(len,ans);
}
cout<<ans<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
#endif
int ncase;
RD(ncase);
while(ncase--)
solve();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.