（未完待续）

题目链接：GMOJ 6288。

题目

给定一个长度为 $n$ 的序列，你可以选择翻转一个任意正整数长度的区间，求翻转后最大的 $\sum _ {i=1}^n[a _ i=i]$。

题解

思路

代码

#include<cstdio>
#include<algorithm>
using std::max;
using std::pair;
using std::make_pair;
const int MAXN=100000+5;
int n;
int sum[MAXN];
pair<int,int> point[MAXN];
int main(void){
    freopen("rotate.in","r",stdin);
    freopen("rotate.out","w",stdout);
    register int i,l,r,temp,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        static int x;
        scanf("%d",&x);
        point[i]=make_pair(x+i,max(x,i)-(x+i)/2);
        sum[i]=sum[i-1]+(i==x);
    }
    sort(point+1,point+n+1);
    for(i=1,temp=0;i<=n;++i){
        l=point[i].first/2-point[i].second;
        r=point[i].first-l;
        temp=point[i].first==point[i-1].first?temp+1:1;
        if(point[i].second)
            ans=max(ans,sum[l-1]-sum[r-1]+temp);
    }
    printf("%d\n",ans+sum[n]);
    return 0;
}