首页 > 代码库 > hoj_10027_优化DP（LIS）

hoj_10027_优化DP（LIS）

2024-07-05 00:26:23   222人阅读

Longest Ordered Subsequence Extention
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 778, Accepted users: 555
Problem 10027 : No special judgement
Problem description

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Please notice this problem is different with 10001,^_^.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 100000 each, separated by spaces. 1 <= N <= 50000



Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.



Sample Input
7
1 7 3 5 9 4 8
Sample Output
4

 

  起初，我愚蠢的以为这道题和10001一样，仅仅把数组开大，然后就WA了。

  很感谢yiyi学长教我写这道题。n=50000，要优化为一个O(n*logn)的DP，用到二分查找。

  二分法是中学解方程的时候常用的方法，也是ACM中查找某个满足条件的值的方法，当数据量很大适宜采用该方法。注意的是，采用二分法查找时，数据需是排好序的。

  基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
 
  基本思路：另外开一个数组b[N](k)，记录最优的lis。维护的过程中，if(a[i] > b[k]) b[k++] = a[i];(如果a[i]比b数组最后一个元素大，就将a[i]放到b数组后面)；if(a[i] < b[k]) b[Check(a[i])] = a[i];(如果a[i]比b数组最后一个元素小，那么就替换掉不小于它的最小的元素)。这样，k的值就是对应的lis的值。1 7 3 5 9 4 8

  拿样例来说，b数组中元素的变化：

  1
  1 7
  1 3
  1 3 5
  1 3 5 9
  1 3 4 9
  1 3 4 8

 

  因此 k = 4 。

  其中，Check函数就是用了二分查找，但是要注意到left和right对结果的影响。
 
  下面是AC代码：
 
 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7 
 8 using namespace std;
 9 
10 int Check(int *p);
11 
12 int N;
13 int i, j, k;
14 int a[50005];
15 int b[50005];
16 
17 int main()
18 {
19     while(scanf("%d",&N)!=EOF) {
20 
21         memset(b, 0, sizeof(b));
22 
23         k = 0; b[0] = -1;  // 初始化b[0]为-1
24 
25         for(i=0; i<N; i++) {
26 
27             scanf("%d",&a[i]);
28 
29             if(a[i] > b[k])  b[++k] = a[i];  // 大于b[k]的元素直接放在其后面
30 
31             else if(a[i] < b[k])  b[Check(a[i])] = a[i];  // 替换大于它的最小的元素
32 
33             else ;
34         }
35 
36         printf("%d\n",k);  // k+1就是对应的最长子序列长度
37     }
38 
39     return 0;
40 }
41 
42 int Check(int p)  // 二分查找
43 {
44     int mid;
45     int temp = k;
46     int l = 0, r = k;
47 
48     while(l <= r) {
49 
50         mid = (l + r)/2;
51 
52         if(b[mid] >= p) { temp = min(mid, temp); r = mid - 1; }
53 
54         else  l = mid + 1;
55     }
56 
57     return temp;
58 }

 

 


联系
我们