[单调队列] UVA 10534 Wavio Sequence

关键在于正确性和最优性的证明：

正确性：通过单调队列的维护，不会得到比实际最长串更大的长度；

最优性：通过单调队列的维护，能得到不小于最长串的长度；

　　实际存在的最长串在出现之后，单调队列的长度不会小于这个最长串的长度（替换不改变长度，只有进队时增加了长度），而之前出现的较大的队列尾会被替换，较小的会被较大的通过入队的方式更新。

 1 /*
 2     UVA 10534 - Wavio Sequence
 3 */
 4 # include <cstring>
 5 # include <cstdio>
 6 
 7 # define N 10000 + 5
 8 
 9 int n;
10 int a[N];
11 int f[N], g[N];
12 
13 int max(int x, int y)
14 {
15     return x>y ? x:y;
16 }
17 
18 int min(int x, int y)
19 {
20     return x<y ? x:y;
21 }
22 
23 void init(void)
24 {
25     for (int i = 1; i <= n; ++i)
26         scanf("%d", &a[i]);
27 }
28 
29 int bin_search(int *v, int key, int n)
30 {
31     int high = n, low = 1, mid;
32     while (low < high)
33     {
34         mid = low + ((high-low)>>1);
35         if (v[mid] < key) low = mid+1;
36         else if (v[mid] == key) return mid;
37         else high = mid;
38     }
39     return low;
40 }
41 
42 void compute(int *d, int inc, int ss, int tt)
43 {
44     int s[N], top = 0;
45     for (int i = ss; i != tt; i += inc)
46     {
47         int &t = a[i];
48         if (t>s[top]) s[++top] = t;
49         else
50         {
51             int k = bin_search(s, t, top);
52             s[k] = t;
53         }
54         d[i] = top;
55     }
56 }
57 
58 void solve(void)
59 {
60     compute(f, 1, 1, n);
61     compute(g, -1, n, 1);
62     int ans = 0, tmp;
63     for (int i = 1; i <= n; ++i)
64     {
65         int tmp = min(f[i], g[i]);
66         if (ans < tmp) ans = tmp;
67     }
68     printf("%d\n", ans*2-1);
69 }
70 
71 int main()
72 {
73     while (~scanf("%d", &n))
74     {
75         init();
76         solve();
77     }
78     
79     return 0;
80 }

直接DP复杂度为O（n^2），单调队列的方式为O(n*logn)；

由于单调队列的维护方法，不能得到最长子列，而只能得到其长度。