2020-08-14

http://icpc.upc.edu.cn/problem.php?cid=2526&pid=5

题目描述

在曾经的讲解中，花和他的兄弟姐妹们被这个叫做 Yyx 的人摆来摆去，吓得耳朵都瞎了，嘴巴也听不见了。于是他们决定「以其人之道还治其人之身」，他们把 Yyx, Kangkang, Michael 等人摆成一排，这个时候，花说道：「你们的身高太不和谐了，只有满足我的要求的人才能留下，其他人都去当花。」而 Yyx 想留下尽量多的同胞们，于是他来找你了。 具体而言，人的高度可以看成一列整数h1,h2,...,hn。 设当一部分人出去后，剩下的人的高度依次为g1,g2,...,gm ，则花们希望下面两个条件中至少有一个满足： ·条件A ：对于所有 g2i>g2i-1,g2i>g2i+1。 ·条件B ：对于所有 g2i<g2i-1,g2i 1 时最多有一个能满足。

输入

第一行包含一个正整数 n ，表示开始时的人数。 第二行包含 n 个正整数，依次为 h1,h2,...hn , 表示每个人的高度。

输出

输出留下的人数的最大值。

样例输入

5
5 3 2 1 2

样例输出

3

提示

对于所有数据，1≤n≤106,0≤hi≤106

动态规划

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1005000]={0};
ll s1[1005000]={0};
ll s2[1005000]={0};
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    s1[1]=s2[1]=1;
    for(ll i=2;i<=n;i++)
    {
        if(a[i]>a[i-1])
        {
            s1[i]=max(s1[i-1],s2[i-1]+1);
            s2[i]=s2[i-1];
        }
        if(a[i]==a[i-1])
        {
            s1[i]=s1[i-1];
            s2[i]=s2[i-1];
        }
        if(a[i]<a[i-1])
        {
            s2[i]=max(s2[i],s1[i-1]+1);
            s1[i]=s1[i-1];
        }
    }
    printf("%lld\n",max(s1[n],s2[n]));
}