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;}