题解：P15705 [2018 KAIST RUN Spring] Zigzag

fish_ysj · 2026-03-11 19:30:57 · 题解

题解：P15705 [2018 KAIST RUN Spring] Zigzag

题目大意

给定一个长度为 N 的序列 A，求它的一个最长子串 A_l,A_{l+1}\dots A_r，使得对于任意的 l+2\le i \le r 均不存在 A_i \le A_{i-1} \le A_{i-2} 或 A_i \ge A_{i-1} \ge A_{i-2} 的情况。

思路

一道非常基础的简单模拟题。注意到数据范围 N \le 5000，可以直接遍历查找答案。用 ans 变量记录最佳答案，考虑从 i=3 开始遍历，设 l=1，一直往下搜到不满足条件的位置后改变 l 并比较记录答案。每一次循环都判定 A_i,A_{i-1},A_{i-2} 的大小关系，若不存在题目限制的两种情况则将 tmp 变量 +1，表示符合条件的序列长度增加；若是符合题目的限制条件，则与最佳答案比较，并将 tmp 变量设为 2（因为若是当前的 A_i,A_{i-1},A_{i-2} 不满足条件，则下一次可以从序列 A_{i+1},A_i,A_{i-1} 开始考虑，故先设 tmp 为 2）。

最后输出答案即可。

AC Code

初学阶段，建议按照上面思路自行写一遍，直接看代码不利于编程学习。 ::::info[代码]

#include<bits/stdc++.h>
using namespace std;
int n,a[5005],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int tmp=2;
    for(int i=3;i<=n;i++)
    {
        if((a[i]>=a[i-1]&&a[i-1]>=a[i-2])||(a[i]<=a[i-1]&&a[i-1]<=a[i-2]))
        {
            ans=max(ans,tmp);
            tmp=2;
        }
        else{
            tmp++;
        }
    }
    ans=max(ans,tmp);//循环最后别忘了更新答案 
    cout<<ans;
    return 0;
}

::::