ZOJ2136 Longest Ordered Subsequence 模版题
code:
code:
#include <stdio.h> #include <string.h> #define MAXN 1000 int a[MAXN+1]; int f[MAXN+1]; int LIS(int n) { int i, j, max; memset(f,0,sizeof(f)); f[0] = 1; for(i=0; i<n; ++i) { max =0; for(j=0; j<i; ++j) if(a[i] > a[j] && max < f[j]) max = f[j]; f[i] = max + 1; } max = 0; for(i=0; i<n; ++i) if(max < f[i]) max = f[i]; return max; } int main() { int T, i, n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0; i<n; ++i) scanf("%d",&a[i]); printf("%d\n", LIS(n) ); if(T != 0) printf("\n"); } return 0; }
nlogn
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int T; int n; int a[1020]; int id[1020]; while(scanf("%d",&n)==1){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); int len=1; id[1]=a[1]; for(int i=2;i<=n;i++){ if(a[i]>id[len]) { id[++len]=a[i]; } else{ int l,r,mid; l=1;r=len; while(l<r){ mid=(l+r)/2; if(a[i]>id[mid]) l=mid+1; else r=mid; } id[l]=a[i]; } } printf("%d\n",len); } }