题解：P15705 [2018 KAIST RUN Spring] Zigzag

zhang_kevin · 2026-03-11 18:12:43 · 题解

枚举起始位置，然后暴力扩展找最靠后的合法结尾，时间复杂度 \mathcal{O}(n^2)。

#include<bits/stdc++.h>
// #define int long long
#define fo(i, l, r) for(int i = (l); i <= (r); i++)
#define fd(i, l, r) for(int i = (l); i >= (r); i--)
#define fu(i, l, r) for(int i = (l); i <  (r); i++)
#define y1 zhang_kevin
#define pii pair<int, int>
#define fi first
#define se second
#define vec vector
#define pb push_back
#define eb emplace_back
#define ll long long
#define ull unsigned long long
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define puts wrs
using namespace std;
bool ST;
char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf, obuf[1 << 20], *p3 = obuf;
inline char gc(){
    if(p1 == p2){
        p1 = ibuf, p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
        if(p1 == p2) return EOF;
        return *p1++;
    }
    return *p1++;
}
inline char pc(char ch){
    if(p3 == obuf + (1 << 20)) flush();
    *p3 = ch;
    return *p3++;
}
template<typename type>
inline int rd(type &x){
    x = 0; bool f = 0; char ch = gc();
    while(!isdigit(ch)) f |= ch == '-', ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? x = -x : 0;
}
template<typename type, typename ...T>
inline void rd(type &x, T &...y){rd(x), rd(y...);}
class Flush{public: ~Flush(){flush();}}_;
template<typename type>
inline void wr(type x){
    if(x < 0) pc('-'), x = -x;
    if(x > 9) wr(x / 10);
    pc(x % 10 + '0');
    return;
}
inline void wrs(string s){for(auto ch : s) pc(ch);}
namespace Solution{
    int n, a[5005];
    inline void Solve(){
        rd(n);
        fo(i, 1, n) rd(a[i]);
        int ans = 0;
        fo(l, 1, n){
            fo(r, l, n){
                int len = r - l + 1;
                if(len > 2){
                    int x = a[r - 2], y = a[r - 1], z = a[r];
                    if((x >= y && y >= z) || (x <= y && y <= z)){
                        break;
                    }
                }
                ans = max(ans, len);
            }
        }
        wr(ans);
        return;
    }
}
bool ED;
signed main(){
    clock_t START = clock();
    // freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
    Solution::Solve();
    cerr << (double)(clock() - START) / CLOCKS_PER_SEC << " s" << '\n';
    cerr << 1.0 * abs(&ED - &ST) / 1024 / 1024 << " MB" << '\n';
    return 0;
}