模拟赛题讲解[19]

来自 yukuai26 2022-08-08 noi.ac #2771

题目背景：

$\text{yukuai26}$ 喜欢爬山，所以他选择绕着山跑圈

题目描述：

$\text{yukuai26}$ 会跑一个环形路径，每个路径有一个高度 $h$，他会顺时针或者逆时针沿着路径跑，一旦确定方向就不会换方向。

由于他喜欢爬山，所以如果前一次跑步时上坡，他希望下一次是下坡，同样的，如果前一次跑步时下坡，下一次他希望是上坡，并且他不希望重复经过同一地点，所以他跑过所有点时就会停下来。

现在 $\text{yukuai26}$ 想知道，他最多可以跑过多少点呢？

一句话题意，给你一个环，环上每个点有一个高度，你要找到其中最长的一条路径 $d_1,d_2….d_l$ , 满足 $d_i$和 $d_{i+1}$ 相邻且所有 $d_i$ 互不相同，且 $h_{d_1} \leq h_{d_2} \geq h_{d_3} \leq h_{d_4}…$或者 $h_{d_1} \geq h_{d_2} \leq h_{d_3} \geq h_{d_4}….$

问最长的 $l$ 是多少。

输入格式：

第一行一个数 $n$ ，表示环形路径的长度

第二行 $n$ 个数 $h_i$ ，表示 $i$ 号点的高度

输出格式：

一行一个数，表示最长的路径长度是多少

输入1：

6
6 2 7 3 5 7

输出1：

输入2：

9
1 7 3 6 8 6 3 1 1

输出2：

数据范围：

对于 $50$% 的数据 $n \leq 100$

对于 $70$% 的数据 $n \leq 1000$

对于 $100$% 的数据 $n \leq 10^5$ ， $h_i \leq 10^4$

题解：

首先断环为链。

注意到以 $i$ 为起点的极大合法段，设其为 $[i,i+\text{sz}_i-1]$

不难发现 $\forall x \in [i,i+\text{sz}_i-1]$ ，$x$ 与 $i$ 重合的那种合法段是一样的。

这里的重合指的是以 $i$ 为起点的那个子段在 $x$ 处切一刀，分割线到 $i+\text{sz}_i-1$ 的那一段。

设 $f_{i,0/1}$ 表示以 $i$ 结尾的极大路径，下一个要朝上走还是朝下走

$f_{i,0} = \max\{1,(f_{i-1,1}+1)\times [a_{i-1}\le a_i]\} \\f_{i,1} = \max\{1,(f_{i-1,0}+1)\times [a_{i-1}\ge a_i]\}$

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

int n,a[N],f[N][2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i],a[i+n]=a[i];
    f[1][0]=f[1][1]=1;
    for(int i=2; i<=(n<<1); i++)
    {
        f[i][0]=f[i][1]=1;
        if(a[i-1]<=a[i]) f[i][0]=max(f[i][0],f[i-1][1]+1);
        if(a[i-1]>=a[i]) f[i][1]=max(f[i][1],f[i-1][0]+1);
    }
    int res=0;
    for(int i=1; i<=(n<<1); i++)
        res=max(res,max(f[i][0],f[i][1]));
    cout << min(n,res) << '\n';
    return 0;
}