链接：

https://codeforces.com/contest/1272/problem/D

题意：

You are given an array a consisting of n integers.

You can remove at most one element from this array. Thus, the final length of the array is n−1 or n.

Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.

Recall that the contiguous subarray a with indices from l to r is a[l…r]=al,al+1,…,ar. The subarray a[l…r] is called strictly increasing if al<al+1<⋯<ar.

思路：

正着反着算一边，能往两边延长的最大长度，对每个点特判。

代码：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+10;

int Dp[MAXN], a[MAXN], Dpr[MAXN];

int n;

int main()

{

    cin >> n;

    for (int i = 1;i <= n;++i)

        cin >> a[i];

    int ans = 1;

    Dp[0] = Dpr[n+1] = 0;

    Dp[1] = Dpr[n] = 1;

    for (int i = 2;i <= n;++i)

    {

        if (a[i] > a[i-1])

            Dp[i] = Dp[i-1]+1;

        else

            Dp[i] = 1;

    }

    for (int i = n-1;i >= 1;--i)

    {

        if (a[i] < a[i+1])

            Dpr[i] = Dpr[i+1]+1;

        else

            Dpr[i] = 1;

    }

    for (int i = 2;i <= n;++i)

    {

        ans = max(ans, Dp[i]);

        if (a[i] > a[i-2])

            ans = max(ans, Dp[i-2]+Dpr[i]);

    }

    cout << ans << endl;

    return 0;

}

巴特西

Codeforces Round #605 (Div. 3) D. Remove One Element（DP）

链接：

题意：

思路：

代码：

最新文章

热门文章