思路: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<
|