点击打开链接

题意:求f(i,j)=ai+aj+abs(i-j)的最大值,i,j<=1e5  =(a[i]+i)+(a[j]-j) (i>j)  枚举下标大的a[i]后,在1~i-1中找到最大的(a[j]-j)即可  pos[i]和a[i]配对的最大a[j]-j的下标  #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> using namespace std; typedef long long ll; typedef vector<int> vec; typedef vector<vec> mat; const int N=1e5+20; const ll mod=400; int a[N],pos[N]; int main() { int t; cin>>t; while(t--) { int n,p=0; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); ll ans=a[1]+a[2]+1; pos[2]=1; for(int i=3;i<=n;i++) { ll t1=a[i]+a[i-1]+1;//i-1 ll t2=a[i]+a[pos[i-1]]+(i-pos[i-1]);//i-1之前 if(t1>t2) { pos[i]=i-1; } else { pos[i]=pos[i-1]; } if(max(t1,t2)>ans) ans=max(t1,t2); } cout<<ans<<endl; } return 0; }