TIOJ-1441

2qbingxuan

2019-12-31

TIOJ , greedy

萬里長城

https://tioj.ck.tp.edu.tw/problems/1441

Description

給定一個序列，找出最長的「長城」子序列
一個序列$< a_1,a_2,\dots,a_n >$必須符合下列幾點才算是「長城」

n是奇數
若$i$是偶數，則$a_i$必須小於相鄰的項
若$i$是奇數，則$a_i$必須大於相鄰的項

Solution

貪心法
維護一個tail表示前$i$項滿足點2. 3.的最佳解，其結尾是多少
假設下一個項h必須比tail大
若h比tail大，那就直接接上去(並更新tail)，否則就把tail替換成h
反之亦然

證明大概可以用數歸吧(?)我也不太會說明QQ

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, tail = -1, inc = 1, ans = 0;
    cin >> n;
    while(n--) {
    	cin >> h;
        if(h == tail) continue;
        if(h < tail ^ inc) ++ans, inc = !inc;
        tail = h;
    }
    if(inc) --ans;
    cout << ans << '\n';
}