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