HDU-1950 Bridging signals (nlogn求LIS)

题目链接：

HDU - 1950

题目大意：

题意！?不懂！真的看不懂！ 我是在学 O(nlogn)求最长上升子序列(LIS) 的博客上看的题意， T组数据，每组一个n，n个数。就是让求LIS ！还整些啥乱七八糟的情景！反正我是没看懂！

数据范围：

T没给，(1≤n≤40000)

解题思路：

nlogn求LIS的板子题，学咯！ 学了就要能用。 定义数组 d，d[i]记录长度为i的LIS 的末位（最后一个）元素。若有多个长度相同的 LIS ，则记录最小的末位元素。这个稍微想想都能明白，记录的末位元素尽可能小，就越可能得到更长的 LIS 。 这个博客写得很清楚： http://blog.csdn.net/shuangde800/article/details/7474903

另附代码：

#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; const int MaxN = 4e4; int T, n; int a[MaxN + 5]; int d[MaxN + 5]; //d[i]记录长度为i的LIS 的末位元素 //若有多个长度相同的LIS,则记录最小的末位元素 int len; int bin_search(int x) //查找d数组中第一个大于等于x的位置 { int l = 0, r = len; int mid = 0; int ans = 0; while(l <= r) { mid = (l + r) >> 1; if(d[mid] >= x) ans = mid, r = mid - 1; else l = mid + 1; } return ans; } int main() { scanf("%d", &T); while(T--) { len = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) { if(a[i] > d[len]) d[++len] = a[i]; else { int pos = bin_search(a[i]); d[pos] = a[i]; } } printf("%d\n", len); memset(a, 0, sizeof(a)); memset(d, 0, sizeof(d)); } return 0; }

里面的bin_search()函数，就是找到d数组中第一个大于等于a[i] 的位置（相当于lower_bound），找到之后用a[i] 将那个位置的元素替换。