自动搬运

查看原文

来自洛谷，原作者为

	syf2008 **

搬运于2025-08-24 22:21:57，当前版本为作者最后更新于2020-06-29 22:02:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题我看题解的各位大佬用了dp,本蒟蒻来一发结构体

这题最难的就是思想

1. 首先你得知道这题要用upper_bound
2. 你如果像我用结构体，那你一定要会用sort结构体排序或者你也可以用题解的dalao用树状数组

上代码

#include <bits/stdc++.h>
using namespace std;
struct ss
{
	int a,i;
}b[100005];//建立结构体
int zhuan(ss a,ss b)//sort要用
{
	if(b.a==a.a)
	return b.i<a.i;
	return b.a>a.a;
}
int d[100005],ss,s=0,n,maxn=1;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{cin>>ss;//输入
	if(ss<=i)//如果它的值小于编号，如果值大于编号，是不可能有价值，屏蔽
	{b[++s].a=ss;
	b[s].i=i-ss;}//i-ss是求他到有价值的差}
	if(!s)//如果没有一个可能有价值
	{cout<<0<<endl;return 0;}
	sort(b+1,b+s+1,zhuan);
	d[1]=b[1].i;
	for(int i=2;i<=s;i++)
	{
	int v=upper_bound(d+1,d+maxn+1,b[i].i)-d;//二分查找
	d[v]=b[i].i;
	maxn=max(v,maxn);//比对
	}
	cout<<maxn<<endl;
}