好贷网好贷款

poj 1631 Bridging signals 最长上升子序列的O(n*lgn)方法

发布时间:2016-12-3 6:16:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1631 Bridging signals 最长上升子序列的O(n*lgn)方法",主要涉及到poj 1631 Bridging signals 最长上升子序列的O(n*lgn)方法方面的内容,对于poj 1631 Bridging signals 最长上升子序列的O(n*lgn)方法感兴趣的同学可以参考一下。

在普通动规基础上,设一个数组d[i],表示到现在为止长度为i的子序列的末尾数字的最小值.显然对于求最长上升子序列由b[i-1] <= b[i] 则b为有序的,可以只用折半查找,从O(n)降到O(nlgn) 。整体时间由 O(n*n) 降到 O(n * lgn). 代码: #include <stdio.h> #include <iostream> #include <cstring> using namespace std; int n; #define MAX_N 40001 int N[MAX_N]; int bl=0; int b[MAX_N]; int dp[MAX_N]; /* O(n2) int solve() { int ret =0; dp[0]=0; for(int i=1;i<=n;i++) { int maxl = 0; for(int j=1;j<i;j++) { if(N[j] < N[i] && dp[j] > maxl) maxl = dp[j]; } dp[i] = maxl+1; if(dp[i] > ret) ret = dp[i]; } return ret; } */ // O(n lg n) 优化 引入b[n]数组 // b[i] d[i],表示到现在为止长度为i的子序列的末尾数字的最小值. 显然对于求最长上升子序列由b[i-1] <= b[i] 则b为有序的,可以只用折半查找,从O(n)降到O(nlgn) 。整体时间由 O(n*n) 降到 O(n * lgn) // void dump() { printf("--------------- b is ------------\n"); for(int i=0;i<=bl;i++) { printf("[%d]=%d\t",i,b[i]); } printf("\n"); } int solve() { int ret =0; dp[0]=0; memset(b,0,sizeof(b)); b[0]=0; bl=0; for(int i=1;i<=n;i++) { int l=1,r=bl; int nl=0; while(l <= r) { int h=(l+r)/2; if(b[h] < N[i]) { l=h+1; } else if(b[h] > N[i]) { r=h-1; } } nl = l; dp[i] = nl; //dump(); //printf("N[%d]=%d l=%d nl=%d\n",i,N[i],l,nl); if( b[ nl] == 0) bl++; if( b[nl] == 0 || N[i] < b[ nl ] ) { //printf("\tb[%d]=%d\n\n",nl,b[nl]); b[ nl ] = N[i]; } } return bl; } int main() { int t; cin>>t; for(int _t=1;_t<=t;_t++) { cin>>n; for(int i=1;i<=n;i++) cin>>N[i]; cout<<solve()<<endl; } }

上一篇:安卓开发37:自定义的HorizontalScrollView类,使其pageScroll的时候焦点不选中
下一篇:HDOJ 2435 - There is a war 枚举+最小割

相关文章

相关评论