最长不下降子序列 O(nlogn) || 记忆化搜索

 1 #include<stdio.h>
 2 int a[1000] , temp[1000] ;
 3 int n , top ;
 4 
 5 int binary_search (int x) {
 6     int fir = 0 ;
 7     int last = top ;
 8     int mid ;
 9     while (fir <= last ) {
10         mid = (fir + last) / 2 ;
11         if ( x <= temp[mid] ) {
12             last = mid - 1;
13         }
14         else {
15             if (x <= temp[mid + 1] )
16                 return mid + 1 ;
17             else
18                 fir = mid + 1 ;
19         }
20     }
21 }
22 
23 int main () {
24   //  freopen ("a.txt" ,"r" , stdin) ;
25     while ( scanf ("%d" , &n ) != EOF ) {
26         for (int i = 0 ; i < n ; i++ ) {
27             scanf ("%d" , &a[i]) ;
28         }
29 
30         top = 0 ;//目前最长不下降子序列的长度
31         temp[top] = a[0] ;////temp[i]为长度为i的上升子序列末尾元素的最小值
32         for (int i = 1 ; i < n ; i++ ) {
33             if ( a[i] >= temp[top] ) {
34                 temp[++top] = a[i] ;
35             }
36             else {
37                 if ( a[i] < temp[0] ) {
38                     temp[0] = a[i] ;
39                 }
40                 else {
41                     temp[binary_search(a[i])] = a[i] ;
42                 }
43             }
44         }
45         printf ("%d
" , top + 1) ;
46     }
47     return 0 ;
48 }

用二分查找法

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<vector>
 4 #include<algorithm>
 5 const int inf = 0x3f3f3f3f ;
 6 std::vector <int> g[1000 + 10] ;
 7 int a[1111] ;
 8 int dp[1111] ;
 9 int n ;
10 
11 int dfs (int id , int dep )
12 {
13     if (dp[id] != 1) return dp[id] ;
14     if (id == n - 1) return dp[id] ;
15     bool flag = 0 ;
16     for (int i = id + 1 ; i < n ; i ++) {
17         if (a[i] > a[id]) {
18             g[dep].push_back (dfs ( i , dep + 1) ) ;
19             flag = 1 ;
20         }
21     }
22     if (flag) {
23         int t = max_element (g[dep].begin () , g[dep].end () ) - g[dep].begin () ;
24         dp[id] += g[dep][t] ;
25         g[dep].clear () ;
26     }
27     return dp[id] ;
28 }
29 
30 int main ()
31 {
32    // freopen ("a.txt" , "r" , stdin ) ;
33     while ( ~scanf ("%d" , &n) ) {
34         memset (dp , 0 , sizeof(dp)) ;
35         for (int i = 0 ; i < n ; i ++) scanf ("%d" , &a[i]) ;
36         for (int i = 0 ; i < n ; i ++) dp[i] = 1 ;
37         for (int i = n - 2 ; i >= 0 ; i --) { dfs (i , 0) ;  }
38         int len = -inf ;
39         for (int i = 0 ; i < n ; i ++) len = std::max (len , dp[i]) ;
40         printf ("%d
" , len ) ;
41     }
42     return 0 ;
43 }

记忆化搜索