都是求最长递增子序列。
这里贴个模板。
POJ 1631.
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 2005 #define inf 1<<28 using namespace std; int a[40005]; int main() { int i,j,k,l,m,n,T; cin>>T; while(T--) { cin>>n; int head=0; for(i=1; i<=n; i++) { scanf("%d",&k); if(head==0||k>a[head]) a[++head]=k; else { int high=head; int low=1; while(high>=low) { int mid=(high+low)/2; if(a[mid]<k) low=mid+1; else high=mid-1; } a[low]=k; } } cout<<head<<endl; } return 0; }