問題:
http://poj.org/problem?id=3670思路:
1.
將原問題化解為求最長不下降子序列和最長不上升子序列即可
求解LIS/LDS的nlogn算法
參考
http://www.shnenglu.com/Joe/archive/2010/08/14/123461.html2.
參考:
http://www.byvoid.com/blog/usaco-feb08-silver-eating-together/代碼:
1 /* LIS/LDS: nlogn */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 30001
6 int N, group[MAX_LEN];
7 int aux[MAX_LEN];
8
9 int
10 bin_search1(int *arr, int front, int rear, int target)
11 {
12 int mid;
13 while(front <= rear) {
14 mid = (front+rear)/2;
15 if(aux[mid] <= target)
16 front = mid+1;
17 else
18 rear = mid-1;
19 }
20 return front;
21 }
22
23 int
24 bin_search2(int *arr, int front, int rear, int target)
25 {
26 int mid;
27 while(front <= rear) {
28 mid = (front+rear)/2;
29 if(aux[mid] >= target)
30 front = mid+1;
31 else
32 rear = mid-1;
33 }
34 return front;
35 }
36
37 int
38 LIS() /* LUDS, maybe more accurate, meaning Longest Undecreasing Seq */
39 {
40 int i, len = 1;
41 aux[1] = group[0];
42 for(i=1; i<N; i++) {
43 if(group[i] >= aux[len]) {
44 ++len;
45 aux[len] = group[i];
46 } else {
47 aux[bin_search1(aux, 1, len, group[i])] = group[i];
48 }
49 }
50 return len;
51 }
52
53 int
54 LDS() /* LUIS */
55 {
56 int i, len=1;
57 aux[1] = group[0];
58 for(i=1; i<N; i++) {
59 if(group[i] <= aux[len]) {
60 ++len;
61 aux[len] = group[i];
62 } else {
63 aux[bin_search2(aux, 1, len, group[i])] = group[i];
64 }
65 }
66 return len;
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72 int i, lis_len, lds_len;
73 while(scanf("%d", &N) != EOF) {
74 for(i=0; i<N; i++)
75 scanf("%d", group+i);
76 lis_len = LIS();
77 lds_len = LDS();
78 printf("%d\n", N-(lis_len>lds_len ? lis_len : lds_len));
79 }
80 }