错误情况:第2组数据WA
我的思路是:求最长上升序列(参考B3637),做出如下修改
1、从第一个小于等于当前编号的值开始
2、上升序列不是只要后边比前边大就行,还需要差值大于等于位置差值(保证如果前边的在自己位置上后边的能通过删除若干个或者不删除就在自己的位置上)
代码如下,求分析第2组数据是什么样的内容
#include<iostream>
using namespace std;
int main()
{
long long n,ans=0,i,j,md=-1;
cin>>n;
long long a[n],b[n];
for(i=0;i<n;i++)
{
cin>>a[i];
b[i]=1;
if(md==-1 && a[i]<=i+1)
md=i;
}
if(md==-1)
{
cout<<0;
return 0;
}
for(i=md;i<n;i++)
{
for(j=md;j<i;j++)
if(a[i]>a[j] && a[i]-a[j]<=i-j && b[j]>=b[i])
b[i]=b[j]+1;
if(b[i]>ans)
ans=b[i];
}
cout<<ans;
return 0;
}