HDU OJ 1677 Nested Dolls【二分，LIS】
原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=1677
题意：每组测试数据给n个硬币，现在给你这n个硬币的长和高，若一硬币的长和高都小于另一个硬币，则这来个硬币可嵌套为一个硬币。。求最后剩余的最小硬币数。
思路：首先肯定能想到的是 贪心，不停遍历，不停更新。。复杂度 n*n （超时！！），然后又想到和以前做的题类似，有想到 二分图匹配之最小路径覆盖。。这个题数据20000个点，铁定超时。。看了xiaod的博客，看到一种牛叉的算法。。首先 按照 长 对硬币排序（由大到小），然后对于所有硬币的高组成的一个序列，求最长单调递增子序列的个数，这就是问题的解！仔细想一下，列出求的单调递增序列对应的硬币，发现他们任意两两都是不能嵌套的。然后其余的硬币都可以嵌套进入这些硬币中！这个想法太神奇了……对于求最长单调递增子序列，要是动态规划复杂度n*n，还是要超时的。这里再利用二分查找，复杂度O（n*logn），就能AC了……
代码：
#include <iostream>#include <stdio.h>#include <algorithm>using namespace std;int Ans[22000],sum;struct Doll{ int x; int y; bool operator<(const Doll&t)const { return x>t.x||x==t.x&&y<t.y; }}d[22000];bool cmp(Doll t1,Doll t2){ if(t1.x!=t2.x) return t1.x>t2.x; else return t1.y<t2.y;}void Binary(int dd){ int x=0,y=sum; while(x<y) { int mid = (x+y)/2; if(Ans[mid]>dd) y=mid; else x=mid+1; } Ans[y]=dd;}int main(){ int i,j,n,ncase; cin>>ncase; while(ncase--) { cin>>n; for(i=0;i<n;i++) scanf("%d%d",&d[i].x,&d[i].y); sort(d,d+n); sum=0; Ans[sum++]=d[0].y; for(i=1;i<n;i++) { if(d[i].y>=Ans[sum-1]) Ans[sum++]=d[i].y; else Binary(d[i].y); } cout<<sum<<endl; } return 0;}