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