模拟赛题讲解[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：

5

输入2：

9
1 7 3 6 8 6 3 1 1

输出2：

7

数据范围：

对于 \(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;
}