请问测试点二为什么这么诡异,老是过不了😭😭😭😭下面是我的代码。
简单来说就是先把上升的子序列存起来,看能不能两个子序列连接。
或者直接判定可否加一。😭😭 #include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define db puts("here!")
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1e5+5;
int a[maxn];
struct node{
int st,len;
}dp[maxn];
inline int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
int n,len=0,cnt=0,s=1;
cin>>n;
rep(i,1,n)
{
a[i]=read();
if(a[i]>a[i-1])len++;
else dp[++cnt].st=s,dp[cnt].len=len,len=1,s=i;
if(i==n)dp[++cnt].st=s,dp[cnt].len=len;
}
int ans=0;
rep(i,1,cnt-1)
if(dp[i].len+dp[i+1].len>ans)
if(dp[i+1].len==1)ans=dp[i].len+1;
else if(a[dp[i+1].st-1]<=a[dp[i+1].st+1]-2)
ans=dp[i].len+dp[i+1].len;
else ans=max(ans,dp[i].len+1);
if(cnt==1)ans=dp[1].len;
else if(a[dp[cnt].st]>1)ans=max(ans,dp[cnt].len+1);
else ans=max(ans,dp[cnt].len);
cout<<ans<<endl;
}
改后代码如下:
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define db puts("here!")
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1e5+5;
int a[maxn];
struct node{
int st,len;
}dp[maxn];
inline int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
int n,len=0,cnt=0,s=1;
cin>>n;
rep(i,1,n)
{
a[i]=read();
if(a[i]>a[i-1])len++;
else dp[++cnt].st=s,dp[cnt].len=len,len=1,s=i;
if(i==n)dp[++cnt].st=s,dp[cnt].len=len;
}
int ans=0;
rep(i,1,cnt-1)
if(dp[i].len+dp[i+1].len>ans)
if(dp[i+1].len==1)ans=dp[i].len+1;
else if(a[dp[i+1].st-1]<=a[dp[i+1].st+1]-2||a[dp[i+1].st-2]<=a[dp[i+1].st]-2)
ans=dp[i].len+dp[i+1].len;
else ans=max(ans,dp[i].len+1);
if(cnt==1)ans=dp[1].len;
else if(a[dp[cnt].st]>1)ans=max(ans,dp[cnt].len+1);
else ans=max(ans,dp[cnt].len);
cout<<ans<<endl;
}
全部评论
(1) 回帖