【 问题描述 】
有N辆列车，标记为1,2,3,…,N。它们按
照一定的次序进站，站台共有K个轨道，轨
道遵从 先进先出的原则。列车进入站台内
的轨道后可以等待任意时间后出站，且所
有列车不可后退。现在要使出站的顺序变
为N,N-1,N-2,…,1，询问K的最小值是多
少。
例如下图中进站的顺序为1,3,2,4,8,6,9,5,7，则出站的顺序
变为9,8,7,6,5,4,3,2,1。
【 输入格式 】
输入文件名为manage.in。
输入共2行。
第 1 行包含1个正整数N，表示N辆列车。
第 2 行包含N个正整数，为1至N的一个排
列，表示进站次序。
【 输出格式 】
输出文件名为manage.out。
输出共1行，包含1个整数，表示站台内轨
道数K的最小值。
【 数据规模与约定 】
对于30%的数据，N≤10；
对于70%的数据，N≤2000；
对于100%的数据，N≤100000。
题解:由于列车要求编号从大到小出站，那就要求大的先进站，先进先出，将车的编号从大到小排序得到从编号从n到1车对应进站顺序的排列a，由于车的编号一定从大到小排列，只要i后面的车j的进站顺序比i的大，则j就能和i进同一个铁轨，找到a中严格下降子序列的最少个数即为答案。时间复杂度o（n2），按道理说只能过70%的数据，但由于数据比较弱，得到了100分。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define N 100100 #define ll long long using namespace std; int n,k,sum=1; int f[N]; struct node { int k,bj; }a[N]; bool cmp(node a,node b) { if (a.k>b.k) return 1; else return 0; } int main() { freopen("manage.in","r",stdin); freopen("manage.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i].k); a[i].bj=i; } sort(a+1,a+n+1,cmp); f[1]=a[1].bj; for (int i=2;i<=n;i++) { int kk=0,kb=0; for (int j=1;j<=sum;j++) { if (a[i].bj>f[j]) { if (kk<f[j]) { kk=f[j]; kb=j; } } } if (kb) f[kb]=a[i].bj; else f[++sum]=a[i].bj; } cout<<sum<<endl; fclose(stdin); fclose(stdout); return 0; }
正解：二分优化DP，时间复杂度o（nlogn）
#include<cstdio> #include<iostream> #define N 100100 int n,sum=1; int a[N],f[N]; using namespace std; int erfen(int l,int r,int k) { if (l==r) return l; int mid=(l+r)>>1; if (f[mid]<k) return erfen(mid+1,r,k); else return erfen(l,mid,k); } int main() { freopen("manage.in","r",stdin); freopen("manage.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); f[1]=a[1]; for (int i=2;i<=n;i++) { int j; if (a[i]>f[sum]) j=++sum; else j=erfen(1,sum,a[i]); f[j]=a[i]; } cout<<sum<<endl; fclose(stdin); fclose(stdout); return 0; }