先求出最长非递增子序列和最长非递减子序列，由总长度减去其中较长的一个
1
#include <cstdio>
2#include <algorithm>
3#include <vector>
4#include <list>
5#include <iterator>
6#include <limits>
7using namespace std;
8
9const int SIZE = 30010;
10
11template<typename T>
12int LIS(T Array[], int nCnt)
13
{
14
if (nCnt == 0)
15 return 0;
16
17 Array[nCnt++] = numeric_limits<T>::max();
18
19 T *p = Array;
20 vector<T> dp;
21 dp.push_back(p[0]);
22 int nRet = 1;
23 for (int n = 1; n < nCnt; ++n)
24
{
25 T& e = p[n];
26 typename vector<T>::iterator itor = upper_bound(dp.begin(), dp.end(), e, less<int>());
27
28 if ( itor == dp.end() )
29 dp.push_back(e);
30 else if (*itor > e)
31 *itor = e;
32
}
33
34 return ((int)dp.size() - 1) ;
35
}
36
37template<typename T>
38int LDS(T Array[], int nCnt)
39{
40 Array[nCnt++] = numeric_limits<T>::min();
41
42 T *p = Array;
43 vector<T> dp;
44 dp.push_back(p[0]);
45 int nRet = 1;
46 for (int n=1; n < nCnt; ++n)
47 {
48 T& e = p[n];
49 typename vector<T>::iterator itor = upper_bound(dp.begin(), dp.end(), e, greater<int>());
50
51 if ( itor == dp.end() )
52 dp.push_back(e);
53 else if (*itor < e)
54 *itor = e;
55 }
56
57 return (int)dp.size()-1;
58}
59
60int array[SIZE];
61
62int main()
63{
64 int i, n, lis, lds;
65
66 scanf("%d", &n);
67
68 for ( i = 0; i < n; ++i )
69 {
70 scanf("%d", &array[i]);
71 }
72
73 lis = LIS(array, n);
74 lds = LDS(array, n);
75
76 int ans = (lis > lds ? lis : lds);
77
78 printf("%d\n", n - ans);
79 return 0;
80}