首页 > 代码库 > POJ 1631 Bridging signals（LIS+二分）

POJ 1631 Bridging signals（LIS+二分）

2024-07-04 17:57:06   222人阅读

题目链接：POJ 1631 Bridging signals

【题意】简单来说就是求最长上升子序列的长度。

【思路】这道题目的数据规模有40000之多，如果用普通的动态规划O（n^2）肯定会超时的，所以要用上二分查找（又是二分啊，真牛逼）来进行优化，O（nlogn）的时间复杂度就OK了。

我使用了C++的lower_bound(ForwardIter first, ForwardIter last, const _Tp& val)函数.可以直接查找非递减序列[first, last)中的第一个大于等于值val的位置。

下面贴AC代码：

 1 /*
 2 ** POJ 1631 Bridging signals
 3 ** Created by Rayn @@ 2014/05/06
 4 ** 最长上升子序列
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 using namespace std;
10 const int MAX = 40010;
11 
12 int ans, arr[MAX], dp[MAX];
13 
14 int main()
15 {
16 #ifdef _Rayn
17     freopen("in.txt", "r", stdin);
18 #endif
19 
20     int t, n;
21 
22     scanf("%d", &t);
23     while(t--)
24     {
25         scanf("%d", &n);
26         for(int i=1; i<=n; ++i)
27             scanf("%d", &arr[i]);
28 
29         memset(dp, 0, sizeof(dp));
30         ans = 0;
31         dp[ans++] = arr[1];
32         for(int i=2; i<=n; ++i)
33         {
34             if(arr[i] > dp[ans-1])
35             {
36                 dp[ans++] = arr[i];
37             }
38             else
39             {
40                 int *p = lower_bound(dp, dp+ans, arr[i]);
41                 *p = arr[i];
42             }
43         }
44         printf("%d\n", ans);
45     }
46     return 0;
47 }
View Code

 


联系
我们