竞赛讨论区 > 测试点二 一生之敌
头像
TheOnlyMan
编辑于 2021-02-03 18:14
+ 关注

测试点二 一生之敌

请问测试点二为什么这么诡异,老是过不了😭😭😭😭下面是我的代码。
简单来说就是先把上升的子序列存起来,看能不能两个子序列连接。
或者直接判定可否加一。😭😭 #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) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐