题解：P15705 [2018 KAIST RUN Spring] Zigzag

star_field · 2026-03-11 17:34:09 · 题解

挑战 O(n) 失败了呜呜呜呜呜呜 （其实是懒得写了）。

思路

注意数据范围我们可以 O(n^2) 枚举区间，然后暴力统计。虽然我没有写出 O(n) 的代码，但有思路，也可以参考一下。标记所有 zigzag 序列，最长的合法序列满足：左边开头是整个序列的开头或某个 zigzag 序列的结尾（两个数字），中间均不为 zigzag 序列，结尾为整个序列的结尾或某个 zigzag 序列的开头（两个数字）。O(n) 统计即可。

代码

这是 O(n^2) 的。

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=5005;
ll n,a[N],ans=-1;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){ //暴力枚举区间
            if(j>=i+2&&((a[j-2]>=a[j-1]&&a[j-1]>=a[j])||(a[j-2]<=a[j-1]&&a[j-1]<=a[j]))){ //判断合法性
                ans=max(ans,j-i+0ll); //区间长是 j-i+1，去掉一个不合法数字为 j-i
                break;
            }
            if(j==n) ans=max(ans,j-i+1ll);
        }
    }
    cout<<ans;
    return 0;
}