題目: UVa - 10534 - Wavio Sequence
題目說明
給定一個長度為 n 的整數序列,求一個最長子序列(不一定為連續),使得該序列的長度為奇數 2 * k + 1,前 k + 1 個數嚴格遞增,後 k + 1 個數嚴格遞減。(嚴格遞增 / 遞減意味著相鄰兩個數不能相同)
UVA 10534 - Wavio Sequence LIS_C++入門知識
解題思路
遞增的部分很明顯是 LIS,遞減的部分可以視為反向的 LIS,先做出正向及反向的 LIS,之後遍歷陣列,遍歷到的元素視為中心,可以組出的長度為正向及反向 LIS 的較小值乘 2 加 1 ( 依照題目要求 )。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; ++i) #define CLR(c) memset(c, 0, sizeof(c))
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
const int MXN = 10001;
int N; int l; int n[MXN]; int seq[MXN]; int L[MXN]; int LR[MXN];
void init() { CLR(seq); l = 0; }
void read() { FOR(i, 0, N) cin >> n[i], L[i] = LR[i] = 1; }
void LIS() { FOR(i, 0, N) { int pos = lower_bound(seq, seq + l, n[i]) - seq; seq[pos] = n[i]; L[i] = pos + 1; if (pos == l) ++l; }
init(); for (int i = N - 1; i >= 0; --i) { int pos = lower_bound(seq, seq + l, n[i]) - seq; seq[pos] = n[i]; LR[i] = pos + 1; if (pos == l) ++l; } }
void solve() { int mx = 1; FOR(i, 0, N) mx = max(min(L[i], LR[i]) * 2 - 1, mx); cout << mx << '\n'; }
int main() { while (cin >> N) { read(); init(); LIS(); solve(); } }
|
參考資料
UVA 10534 - Wavio Sequence LIS_C++入門知識