HDU 1025 Constructing Roads In JGShining's Kingdom

动态规划问题，求最长非递减子序列

先用了O(n^2)的算法，结果如预料的一般WA

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define SIZE 500000+5
 6 int a[SIZE];
 7 int res[SIZE];
 8 
 9 int main()
10 {
11 
12     freopen("C:\Users\super\Documents\CB_codes\in.txt", "r", stdin);
13     //freopen("C:\Users\super\Documents\CB_codes\out.txt","w",stdout);
14     int n, m, t, len;
15     int fir = 0;
16     while( ~ scanf("%d", &n) ) {
17         memset(a, 0, sizeof(a) );
18         for(int i = 1; i <= n; ++ i) {
19             scanf("%d%d", &m, &t);
20             a[m] = t;
21         }
22         len = 1;
23         res[1] = 1;
24         for(int j = 1; j <= n; ++ j) {
25             for(int i = 1; i < j; ++ i) {
26                 if(a[j] > a[j-1] && res[j] < res[i]+1)
27                     res[j] = res[i] + 1;
28                 if(len < res[j])
29                     len = res[j];
30             }
31         }
32         if(len == 1) {
33             printf("Case %d:
My king, at most %d road can be built.
", fir+1, len);
34         }
35         else {
36             printf("
Case %d:
My king, at most %d roads can be built.
", fir+1, len);
37 
38         }
39         fir ++;
40     }
41 
42     fclose(stdin);
43     return 0;
44 }

之后又查询了O(n*logn)的算法，其中用到了二分查找

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 #define SIZE 500000+5
  6 int a[SIZE];
  7 int res[SIZE];
  8 int fnd(int a, int l, int h) {
  9     int M = (l + h) / 2;
 10     while(l <= h) {
 11         if(a == res[M])
 12             return M;
 13         else {
 14             if(a > res[M])
 15                 l = M + 1;
 16             else
 17                 h = M - 1;
 18             M = (l + h) / 2;
 19         }
 20     }
 21     return l;
 22 
 23 }
 24 int main()
 25 {
 26 
 27     freopen("C:\Users\super\Documents\CB_codes\in.txt", "r", stdin);
 28     //freopen("C:\Users\super\Documents\CB_codes\out.txt","w",stdout);
 29     int n, m, t, len;
 30     int fir = 0;
 31     while( ~ scanf("%d", &n) ) {
 32         memset(a, 0, sizeof(a) );
 33         for(int i = 1; i <= n; ++ i) {
 34             scanf("%d%d", &m, &t);
 35             a[m] = t;
 36         }
 37         len = 1;
 38         res[1] = a[1];
 39         for(int j = 2; j <= n; ++ j) {
 40             t = fnd(a[j], 1, len);
 41             res[t] = a[j];
 42             if(t > len)
 43                 len ++;
 44         }
 45         if(len == 1) {
 46             printf("Case %d:
My king, at most %d road can be built.

", fir+1, len);
 47         }
 48         else {
 49             printf("Case %d:
My king, at most %d roads can be built.

", fir+1, len);
 50 
 51         }
 52         fir ++;
 53     }
 54 
 55     fclose(stdin);
 56     return 0;
 57 }
 58

---------------- 人们生成的最美好的岁月其实就是最痛苦的时候，只是事后回忆起来的时候才那么幸福。