枚举O($2^n$) 20pts

通过枚举子集的方式枚举所有的选择，然后判断选择是否合法.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int res=0;
    n=unique(a,a+n)-a; //去重
    for(int i=0;i<1<<n;i++)
    {
        vector<int> v;
        for(int j=0;j<n;j++) //将所有序列提取出来
        {
            if(i>>j&1)
            {
                v.push_back(a[j]);
            }
        }
        bool st=0;
        for(int j=1;j+1<v.size();j++) //判断选择序列是否合法
        {
            int x=v[j-1],y=v[j],z=v[j+1];
            if(y>x&&y>z||y<x&&y<z) //合法就判断下一个
            {
                continue;
            }
            else
            {
                st=1;
            }
        }
        if(st==0) //说明合法
        {
            res=max(res,(int)v.size());
        }
    }
    cout<<res;
    return 0;
}

动态规划O($n$) 100pts

类似于状态机

f[i][0] 表示在前1到$i$个数中选，最后是下降的序列个数的最大值

f[i][1]表示在前1到$i$个数中选，最后是上升的序列个数的最大值

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int f[N][2]; //f[i][0]表示到1到i且下降长度的最大值,
//f[i][1]表示到1到i且上升长度的最大值
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    n=unique(a+1,a+n+1)-(a+1); //去重
    f[1][0]=f[1][1]=1;//初始化
    for(int i=2;i<=n;i++)
    {
        if(a[i]>a[i-1])
        {  
            f[i][0]=f[i-1][0]; //当前大于前面一个，下降数量不会变化
            f[i][1]=f[i-1][0]+1; //当前大于前面那个，上升数量在以前下降基础上+1
        }
        else
        {
            f[i][0]=f[i-1][1]+1; //当前小于前面那个，可以以前上升+当前这个下降
            f[i][1]=f[i-1][1]; //变小了，上升的数量不会发生变化
        }
    }
    cout<<max(f[n][0],f[n][1]); //1...n中第n个数上升或者下降的最大值
    return 0;
}

贪心O($n$)100pts

对于原来序列，如果两个数中间有一个数比它两都大，则存在极大值

对于原来序列，如果两个数中间有一个数比它两都小，则存在极小值

那么选取的点的数目是小于等于极值点的数目的[要不然就不符合题目要求]

那么我们选择所有的极值点，容易观察都是符合要求的。所以就是求极值点的数目。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    n=unique(h+1,h+n+1)-(h+1); //相邻的去重
    int res=min(n,2); //首尾
    for(int i=2;i<n;i++)
    {
        int a=h[i-1],b=h[i],c=h[i+1];
        if(b>a&&b>c||b<a&&b<c) //构成V或^
        {
            res++;
        }
    }
    cout<<res;
    return 0;
}