竞赛讨论区 > 如果一直有一个测试点过不去的xdm可以看看这个
头像
Levi_yxc
编辑于 2022-09-27 10:38 北京
+ 关注

如果一直有一个测试点过不去的xdm可以看看这个

,要是 了注意一下最长上升子序列也是可以修改的,只要是没有长度到 的都可以修改一次让这个上升子序列变得更长

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

#define endl '\n'

using namespace std;

typedef long long LL;

const int N = 100010, INF = 0x3f3f3f3f;

int n;
int w[N];
int l[N], r[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    w[0] = INF, w[n + 1] = -1;

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        l[i] = 1;
        if (w[i] > w[i - 1]) l[i] = l[i - 1] + 1;
        if (i < n) res = max(res, l[i] + 1);
        else res = max(res, l[i] + (l[i] < n));
    }

    for (int i = n; i; i -- )
    {
        r[i] = 1;
        if (w[i] < w[i + 1]) r[i] = r[i + 1] + 1;
        if (i > 1) res = max(res, r[i] + 1);
        else res = max(res, r[i] + (r[i] < n));
    }

    for (int i = 1; i <= n; i ++ )
        if (w[i - 1] + 1 < w[i + 1])
            res = max(res, l[i - 1] + r[i + 1] + 1);

    cout << res << endl;

    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐