题目大意

给定长度为 $n$ 的序列 $a_1，a_2，\dots，a_n$。可以删除任意个元素，其余元素保持原顺序并“下落”重新编号。

要求最大化重排后满足 $a_i = i$ 的位置个数。即选出尽可能多的元素，得它们在新序列中位于“正确”的位置。

思路

假设我们保留了原序列中 $m$ 个位置 $p_1 < p_2 < \dots < p_m$。删除其余元素后，新序列第 $i$ 个元素为原序列的 $a_{p_i}$。 需要满足 $a_{p_i} = i$，同时由于 $p_i$ 是第 $i$ 个被保留的元素，必须有 $p_i\ge i$。

对于 $i < j$，有 $a_{p_i} < a_{p_j}$（因为值必须分别为 $i$ 和 $j$），且 $p_i < p_j$。

由 $p_i-a_{p_i} \le p_j- a_{p_j}$ 可推出 $p_i<p_j$。

有了这些性质就好办了，定义 $f[i]$ 表示以原序列第 $i$ 个元素结尾并且能得到的最大满足条件的个数。

转移就很好转移了。

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],ans,f[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]>i) continue;
		for(int j=0;j<i;j++){
			if(a[i]<=a[j]) continue;
			if(a[i]-a[j]<=i-j) f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	cout<<ans;
}

时间复杂度是 $O(n^2)$，那怎么优化呢？可以用树状数组来优化，但树状数组只可以维护 $1\sim i$ 的最大值，所以维护的区间要转换成 $1\sim i$。

$a[i]-a[j] \le i-j$ 可以转换成 $a[i]-i \le a[j]-j$ 可以转换成 $n-a[i]+i \ge n-a[j]+j$，于是就变成求 $1\sim n-a[i]+i$ 的最大值。

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],ans,f[200005],t[200005];
pair<int,int> b[200005];
void add(int i,int d){
	while(i<=200000){
		t[i]=max(t[i],d);
		i+=(i&(-i));
	}
}
int sum(int i){
	int res=0;
	while(i){
		res=max(res,t[i]);
		i-=(i&(-i));
	}
	return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]={a[i],i};
	sort(b+1,b+1+n);
	for(int i=1,j;i<=n;i++,i=j){
		j=i;
		while(b[i].first==b[j].first) j++;
		for(int k=i;k<j;k++){
			if(b[k].first>b[k].second) continue;
			f[b[k].second]=max(f[b[k].second],sum(n-b[k].first+b[k].second)+1);
			ans=max(ans,f[b[k].second]);
		}
		for(int k=i;k<j;k++){
			if(b[k].first>b[k].second) continue;
			add(n-b[k].first+b[k].second,f[b[k].second]);
		}
	}
	cout<<ans;
}

60分代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int a[N], f[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
        f[0] = f[0] + (a[i] == 0 ? 1 : 0);
        for (int j = i; j >= 1; j--)
            f[j] = max(f[j] + (a[i] == i - j ? 1 : 0), f[j - 1]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}