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

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

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

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

代码：

首先是一般的DP： 

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
const int MAX=40001;
int dp[MAX],num[MAX];
int main()
{
	int T;
	cin>>T;
	while(T--){
		int p;
		cin>>p;
		for(int i=0;i<p;i++) cin>>num[i];
		memset(dp,0,sizeof(dp));
		dp[0]=1;
		for(int i=1;i<p;i++){
			int res=0;
			for(int j=0;j<i;j++){
				if(num[j]<num[i]) res=max(res,dp[j]);
			}
			dp[i]=res+1;
		}
		int res=0;
		for(int i=0;i<p;i++) res=max(res,dp[i]);
		cout<<res<<endl;
	}
	return 0;
}

二分的代码：

#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函数返回的指针用来修改其指向的值。