poj 1631 Bridging signals (LIS 最长递增子序列 DP-二分)

题目：http://poj.org/problem?id=1631

思路：LIS 最长递增子序列，如果用一般的动态规划算法，复杂度是O（n^2），题目的数据规模下会超时，采用二分的思想：复杂度是O（nlogn）

代码：

首先是一般的DP：

#include<iostream>#include<cstring>#include<vector>#include<algorithm>#include<cstdlib>using namespace std;const int MAX=40001;int num[MAX],dp[MAX];int main(){int T;cin>>T;while(T--){int p;cin>>p;for(int i=0;i<p;i++) cin>>num[i];//vector<int> dp;int len=0;//dp.push_back(num[0]);dp[len++]=num[0];for(int i=1;i<p;i++){if(num[i]>dp[len-1]) dp[len++]=num[i];else{int *pt=lower_bound(dp,dp+len,num[i]);*pt=num[i];}}cout<<len<<endl;}return 0;}

1楼dahlwuyn昨天 17:05

这对吗？而且也没看出二分法的影子啊

Re: xiaozhuaixifu昨天 17:10

回复dahlwuynnSTL里面的算法 lower_bound是基于二分实现的

Re: dahlwuyn昨天 17:10

回复xiaozhuaixifun那个pt是干嘛用的

Re: xiaozhuaixifu昨天 21:09

回复dahlwuynn函数返回的指针用来修改其指向的值。