HDU 1950 Bridging signals 思维 最长上升子序列的nlogn
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1950
题目描述： 给出n个数， 让你求出最长上升子序列的长度 （n <= 4*1e4）
解题思路： 首相拿到这道题就是DP， 因为以前这就是最基础的DP， 以前的思路是dp(i)表示以a[i]结尾的最长子序列长度， dp(i) = max{ (dp(j)+1 | j < i && a[j] < a[i]) } 这个是O(n^2)的， 但是这道题会T， 所以要拿出nlogn的方法。 创建数组D来维护一个最长上升子序列， 首先将第一个元素添加进去， 往后如果a[i] > d[len] 就将它添加在最后面， 因为这样是肯定会增加最长子序列的长度的， 如果a[i] < d[len] ， 就把它与D中第一个大于它的元素替换掉， 我是这么想的， 可以画图知道， 替换掉的时候会使这个位置的元素尽量的小， 也就更大的可能是最后一个元素会被替换掉更小的元素， 这样当一个介于我刚才说的最后更小元素和原来最后一个元素之间的数的时候， 前者会增加序列的长度， 而后者并不会， 这就是我的想法， 这是严格证明， 今晚回去看
转自： http://blog.csdn.net/darwin_/article/details/38360997
还有就是这个只是正确维护了最长的长度， 最后的D元素并不是最长子序列本身， 因为会存在替换
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 typedef long long LL; using namespace std; const int maxn = 4 * 1e4 + 100; int a[maxn]; int d[maxn]; int main() { int t; scanf( "%d", &t ); while( t-- ) { int n; scanf( "%d", &n ); for( int i = 1; i <= n; i++ ) { scanf( "%d", a+i ); } int cnt = 0; for( int i = 1; i <= n; i++ ) { if( i == 1 ) { d[cnt++] = a[i]; continue; } if( d[cnt-1] < a[i] ) { d[cnt++] = a[i]; } else { int pos = lower_bound( d, d+cnt, a[i] ) - d; d[pos] = a[i]; } } printf( "%d ", cnt ); } return 0; }
思考： 这个nlogn的算法十分的巧妙， 以前都没有注意看， 仔细看起来还是挺有意思的， 所以以后勤动脑， 多思考， 当然题也不能少， 比赛的时候多往这种思路去想想，别不敢想