POJ 1631 Bridging signals 最长上升子序列小结 LIS的O(nlogn)算法

本文主要是介绍POJ 1631 Bridging signals 最长上升子序列小结 LIS的O(nlogn)算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ 1631 Bridging signals

题目分析：
题目要求避免相交，则可转化为对给定的序列求最长上升子序列。

首先使用了dp来求解，复杂度为O(n*n)，在题目的数据范围下超时了…

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[40000];
int num[40000];
int main() {int t;scanf("%d", &t);while (t--) {int p;scanf("%d", &p);for (int i = 1; i <= p; i++) {scanf("%d", &num[i]);dp[i] = 1;}for (int i = 1; i <= p; i++) {for (int j = 1; j < i; j++) {if (num[j] < num[i]) {dp[i] = max(dp[i], dp[j] + 1);}}}int ans = 0;for (int i = 1; i <= p; i++) {//cout << "dp " << dp[i] << endl;ans = max(ans, dp[i]);}//cout << "ans " << ans << endl;cout << ans << endl;}//system("pause");
}

于是参考各类大神们的博客，学习了LIS问题的O(nlogn)算法

LIS问题的O(nlogn)算法

定义ans[k] : 长度为k的上升子序列的最末尾元素，若有多个长度为k的上升子序列，则保存值最小的末尾元素
定义len用于保存ans数组的长度，也即目前能够得到的最长子序列长度
定义num[]数组来保存给定的序列

易得初始化条件为：ans[1]=num[1]， len=1
下面对其余的序列元素进行遍历：

for (int i = 2; i <= n; i++) {新的元素大于目前最长子序列的末尾元素，则添加到序列尾部if (num[i] > ans[len]) {ans[++len] = num[i];}/*否则找到新的元素num[i]所能构成的最长子序列长度，此时num[i]小于原先时候该长度的末尾元素，用num[i]替换原末尾元素*/else {int tmp = binary_search(i);//在ans序列中返回大于num[i]的最小下标ans[tmp] = num[i];}
}

这里有ans[tmp-1]<num[i]<ans[tmp]
注意ans数组是单调的(递增)，在ans中插入新元素时无需挪动(操作为在尾部添加或者替换前面的元素)——也就是说我们可以使用二分查找，将每一个数字num[i]的插入时间优化到O(logn)~~~~~于是算法总的时间复杂度就降低到了O(nlogn)～！
即利用ans数组的单调性，在查找tmp的时候可以二分查找，从而总的时间复杂度为nlogn

AC代码

/*二分搜索-----最长上升子序列nlogn算法
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int num[40001], ans[40001], len;int binary_search(int i) {//在ans序列中返回大于num[i]的最小下标int left, right, mid;left = 1, right = len;while (left < right) {mid = left + (right - left) / 2;if (ans[mid] > num[i])right = mid;else left = mid + 1;}return left;
}
int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &num[i]);}ans[1] = num[1]; len = 1;for (int i = 2; i <= n; i++) {if (num[i] > ans[len]) {ans[++len] = num[i];}else {int tmp = binary_search(i);//使用stl中的lower_bound函数//int tmp = lower_bound(ans + 1, ans + 1 + len, num[i]) -ans; ans[tmp] = num[i];}}cout << len << endl;}
}

注意ans数组形成的序列并不是最长的递增子序列！！！请看上面的ans数组定义！！！

下面是一个简易的示例：

		num 4  2  6  3  1  5
初始化	ans 4
i=2		.   2
i=3		.	2  6
i=4		.	2  3
i=5		.	1  3
i=6		. 	1  3  5
最终结果len=3，即最长的递增子序列长度为3
但1 3 5显然无法从给定序列中构成
ans[1]=1意味着长度为1的递增子序列末尾长度最小为1
ans[2]=3意味着长度为2的递增子序列末尾长度最小为3
ans[3]=5意味着长度为3的递增子序列末尾长度最小为5