#include <cstdio> #include <vector> #include <algorithm> #define PB push_back using namespace std; struct Num { Num() {} Num(int value, int index) : value(value), index(index), before(0) {} bool operator>(const Num & other) const { return value != other.value ? (value > other.value) : (index > other.index); } bool operator<(const Num & other) const { return value < other.value; } int value, index, before; }; inline void adjust(vector<Num> & v) { for (int i = 1; i < v.size(); i++) { v[i].before = (v[i].value != v[i - 1].value) + v[i - 1].before; } } int main() { int N; while (scanf("%d", &N) == 1) { Num num[10000]; for (int i = 0; i < N; i++) { int v; scanf("%d", &v); num[i] = Num(v, i); } vector<Num> up, down; up.PB(num[0]); int before[10000] = {}, after[10000] = {}; for (int i = 1; i < N; i++) { if (num[i] > up.back()) { up.PB(num[i]); } else { *lower_bound(up.begin(), up.end(), num[i]) = num[i]; } adjust(up); before[up.back().index] = up.back().before; } down.PB(num[N - 1]); for (int i = N - 2; i >= 0; i--) { if (num[i] > down.back()) { down.PB(num[i]); } else { *lower_bound(down.begin(), down.end(), num[i]) = num[i]; } adjust(down); after[down.back().index] = down.back().before; } int max = 0; for (int i = 0; i < N; i++) { int len = (before[i] < after[i] ? before[i] : after[i]) * 2 + 1; max = len > max ? len : max; } printf("%d\n", max); } return 0; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2013年8月10日
UVa 10534 - Wavio Sequence
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言