题解：P15705 [2018 KAIST RUN Spring] Zigzag

big_banana · 2026-03-11 17:25:13 · 题解

TLE 代码

暴力遍历每一个子串，然后判断是不是一个 Zigzag 序列，最后取最大值即可。时间复杂度 O(N^3)

#include<bits/stdc++.h>
using namespace std;
bool f;
int a[5005],n,maxn;
int main(){       
    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++){//遍历每一个子段 
            f=1;//假如这是个Zigzag序列 
            for(int k=i;k<=j-2;k++)
                if(a[k]<=a[k+1]&&a[k+1]<=a[k+2]||a[k]>=a[k+1]&&a[k+1]>=a[k+2]){//判断是否是Zigzag序列
                    f=0;//不是Zigzag序列
                    break;
                }
            if(f) maxn=max(maxn,j-i+1);//记录最大值 
        }
    }
    cout<<maxn;//输出 
    return 0;
}

AC 代码

因为 N\le5000，所以 O(N^3) 肯定会超时。

我们可以标记破坏 Zigzag 序列的元素为 0，其余的标记为 1。

然后查看有哪些合法区间，显然若子序列中元素的标记全为 1，则这就是一个合法区间。由于Zigzag 序列的最后两个元素不受限制，所以序列结尾最多可以再接两个元素。若序列结尾没有两个元素，就接 1 个元素或不接元素。

这里给出一个 O(N^2) 的代码。

#include<bits/stdc++.h>
using namespace std;
bool f[5005];
int a[5005],n,maxn;
int main(){
    maxn=2;    
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];//输入部分 
    for(int i=1;i<=n-2;i++){//遍历每个元素 
        //若这个元素导致序列不是Zigzag序列，则将元素标记为0，否则标记为1 
        if(a[i]<=a[i+1]&&a[i+1]<=a[i+2]||a[i]>=a[i+1]&&a[i+1]>=a[i+2]) f[i]=0;
        else f[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(!f[i]) continue;//a[i]=0，直接跳过 
        int sum=1,j;//初始计数器为1，因为a[i]本身为1 
        for(j=i+1;j<=n&&f[j];j++)
            sum++;//元素为1，计数器加1 
        maxn=max(maxn,sum+min(n-j+1,2));
        //取最大值，并在结尾加上最多两个元素 
    }
    cout<<maxn;
    return 0;
}