【题目描述】 有N个数，求最长上升子序列。 【输入格式】 第一行一个整数N 第二行N个整数表示N个数 【输出格式】 一个整数表示最长上升子序列的最大长度 【样例输入】 5 1 3 2 5 6 【样例输出】 4 【样例解释】 1-3-5-6或1-2-5-6 【数据范围】 对于70%的数据，1<=N<=1000 对于100%的数据，1<=N<=100000 【分析】 对于70%的数据，不难想到令f[i]表示以第i个数结尾的最长上升子序列的长度，第i个数一定是接在之前的某一个序列的后面，故枚举j=1..i-1找到最大的f[j]，f[i]:=f[j]+1，最后输出f[1..n]中的最大值即可。 那对于100%的数据呢？ 从数据范围就可以看出，应该用n log n的算法解决。 维护一个栈Stack，若当前数k大于栈顶的数就压栈，否则二分查找出一个mid使得Stack[mid-1] <= k < Stack[mid]，将k赋给Stack[mid]即可。最后输出栈中元素的个数。 可能有人感到奇怪：无序的序列也能二分查找？注意，这里是在Stack里查找，在这个栈里所有元素都是有序的，这从k的赋值也可以体现。 但是如果要输出该序列中的元素，这个算法就要修改了。
var n,i,t:longint; a,s:array[-1..100000] of longint; function find(l,r:longint):longint; var mid:longint; begin while l<=r do begin mid:=(l+r) shr 1; if (s[mid]>a[i])and(s[mid-1]<=a[i]) then exit(mid); if s[mid]<a[i] then l:=mid+1 else r:=mid-1; end; exit(l); end; begin read(n); for i:=1 to n do read(a[i]); t:=1; s[1]:=a[1]; for i:=2 to n do if a[i]>s[t] then begin inc(t); s[t]:=a[i]; end else s[find(1,t)]:=a[i]; write(t); end.下面看一些例题。
【题目描述】 有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。没对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。 【输入格式】 第1行，一个整数N（1<=N<=100000），表示城市数。 第2行到第n+1行，每行两个整数，中间用一个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。（0<=xi<=10000） 【输出格式】 仅一行，输出一个整数，表示政府所能批准的最多申请数。 【样例输入】 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 【样例输出】 4 【分析】 这题很明显，对a数组排序，然后对b数组求最长上升子序列即可。 算法1：双重循环
uses math; var i,j,n,ans,maxx:longint; a,b,f:array[0..5001]of longint; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; temp:=b[i];b[i]:=b[j];b[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin readln(n); for i:=1 to n do readln(a[i],b[i]); qsort(1,n); f[1]:=1; ans:=1; for i:=2 to n do begin maxx:=0; for j:=i-1 downto 1 do if b[j]<b[i] then maxx:=max(maxx,f[j]); f[i]:=maxx+1; ans:=max(ans,f[i]); end; write(ans); end.算法2：二分查找
uses math; var i,j,n,t:longint; a,h,f,s:array[0..100001]of longint; function find(l,r:longint):longint; var mid:longint; begin while l<=r do begin mid:=(l+r) shr 1; if (a[mid]>h[i])and(a[mid-1]<=h[i]) then exit(mid) else if a[mid]<h[i] then l:=mid+1 else r:=mid-1; end; exit(l); end; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; temp:=h[i];h[i]:=h[j];h[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin readln(n); for i:=1 to n do readln(a[i],h[i]); qsort(1,n); t:=1; fillchar(a,sizeof(a),0); a[1]:=h[1]; for i:=2 to n do if h[i]>a[t] then begin inc(t); a[t]:=h[i]; end else a[find(1,t)]:=h[i]; writeln(t); end.【题目描述】 考虑一个给出为N维空间“箱子”的尺度问题。当有两个尺度时，箱子（2，3）表示这个箱子长度为2个单位，宽度为3个单位。当有三个尺度时，箱子（4，8，9）表示这个箱子长度是４个单位，宽度是８个单位，高度是９个单位。当它有６个尺度时，也许，它表现的是不易了解的箱子（4，5，6，7，8，9）；但是我们能分析这个箱子的特性，例如它的各个尺度。在这个问题中你将分析许多关于Ｎ维空间的箱子，并解决这些箱子的最大的嵌套问题。箱子Ｄ =（d1,d2,…,dn），箱子E = （e1,e2,…,en），di和ei都可以重新排列整理，那么当它们重新排列整理后，箱子D所有的尺度都小于箱子E所有的尺度，那么箱子D可以放入箱子E中。 例如，箱子D =（2，6），当D重新排列整理成（6，2），则可放入箱子E =（7，3）中，此时D每个尺度都小于E的相应尺度。如果D经过重新整理后D =（9，7，5，3），则不可以放入箱子E =（10，8，6，2）中，但是F =（9，5，7，1），重新整理后F =（9，7，5，1），即符合F放入E的条件。 【输入格式】 第一行有两个整数，第一个整数为箱子的总数K，第二个整数为每个箱子的空间维数N。以下K行，每行表示一个箱子，有N个尺度数据，数据间用一个或数个空格分开。（K ≤ 100000，N ≤ 10） 【输出格式】 一个整数，输出最大箱子嵌套数目。 【样例输入】 5 2 3 7 8 10 5 2 9 11 21 18 【样例输出】 5 【分析】 和上一题很相似，只不过上一题只有2个维度，而这题有N个维度。 算法1：读入的时候把1个箱子的N个维度排序，然后按照任意一个维度将K个箱子排序，然后就是最长上升子序列了。
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int a[10010][10]; int f[10010]; int n,m; void qsort(int l,int r){ int i=l,j=r,mid=a[(l+r)/2][1]; while (i<=j) { while (a[i][1]>mid) i++; while (a[j][1]<mid) j--; if (i<=j) { for (int k=1;k<=m;k++) { int tmp=a[i][k]; a[i][k]=a[j][k]; a[j][k]=tmp; } i++;j--; } } if (l<j) qsort(l,j); if (i<r) qsort(i,r); } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) scanf("%d",&a[i][j]); for (int j=1;j<m;j++) for (int k=j+1;k<=m;k++) if (a[i][j]>a[i][k]) { int tmp=a[i][j];a[i][j]=a[i][k];a[i][k]=tmp; } } qsort(1,n); f[1]=1; for (int i=2;i<=n;i++){ f[i]=1; int max=0; for (int j=1;j<=i;j++){ bool flag=true; for (int k=1;k<=m;k++) if (a[i][k]>=a[j][k]) flag=false; if (!flag) continue; if (max<f[j]+1) max=f[j]+1; } if (f[i]<max) f[i]=max; } int max=0; for (int i=1;i<=n;i++) if (max<f[i]) max=f[i]; cout<<max; }算法2：排序之类的跟算法1相同，不同的只有多了一个二分查找。这里用指针实现更方便。代码请支付￥100查看。
转载于:https://www.cnblogs.com/JRX2015U43/p/6533471.html
