|
思路：LIS 最长递增子序列，如果用一般的动态规划算法，复杂度是O（n^2），题目的数据规模下会超时，采用二分的思想：复杂度是O（nlogn）
代码：
首先是一般的DP：
#include
#include
#include
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>num[i];
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i
二分的代码：
#include
#include
#include
#include
#include
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>num[i];
//vector dp;
int len=0;
//dp.push_back(num[0]);
dp[len++]=num[0];
for(int i=1;idp[len-1]) dp[len++]=num[i];
else{
int *pt=lower_bound(dp,dp+len,num[i]);
*pt=num[i];
}
}
cout<
|