poj1631 Bridging signals 加强版最长上升子序列
A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.
#include<iostream>#include<cstdlib>#include<stdio.h>#include<memory.h>#define N 40005using namespace std;int a[N];int b[N];int n;void solve(){ b[1]=a[0]; int maxn=1; for(int i=1;i<n;i++) { int l=1; int r=maxn; int mid; while(l<=r) { mid=(l+r)/2; if(b[mid]<a[i]) l=mid+1; else r=mid-1; } b[l]=a[i]; if(l>maxn) maxn=l; } cout<<maxn<<endl;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); solve(); }}
