先把二位的转化为一维，对数据按W递增排序，按H递减排序，即把二维转化成一维的情形了，因为只有后面的才能套住前面的。。。。
然后从第一个开始往后套，并把已经被套的DOLLS标记，防止第二次被套，如此反复就可以了
大家可以参考一下我的思路：
int flag[20001];
        int sum=0;
        int cur_x,cur_y;
        memset(flag,0,sizeof(flag));
        for(i=0;i<m;i++)
        {
            if(flag[i])
               continue;
            cur_x=n[i].x,cur_y=n[i].y;
            for(j=i+1;j<m;j++)
            {
                if(cur_x<n[j].x&&cur_y<n[j].y&&!flag[j])
                {
                    cur_x=n[j].x;
                    cur_y=n[j].y;
                    flag[j]=1;
                }
            }
            sum++;
        }
        printf("%d\n",sum);
    }
关于二分的算法是这样的：
用数组opt保存当前找到的每个DOLLS堆的最大的DOLL的H值
len表示当前找到DOLLS堆的数目，每次对opt进行二分查找，即找到比当前DOLL的H值小而且最大的，如果没有找到，就把当前的DOLL的H值加入到opt数组中（即二分表中），二分表长度即是DOLLS堆的数目（len值）加1
这样最后len就是所求答案了，先排序，顺序前面已经讲过了，排好就只要对H值操作即可
我的部分代码供参考：
for(i=0;i<n;i++)
		{
			cur=ns[i].y;
			int left=0;
			int right=len; 
			while(left<right)
			{
				int mid=(left+right)/2;
				if(opt[mid]>=cur)
					left=mid+1;
				else right=mid;
			}
			if(len==left)
				len++;
			opt[left]=cur;
		}

• Re:为什么要按W递增，H递减？ 我是按W和H同时递增的。 (34) gzw_02 2008-07-20 09:01:59
  • 试试这组数据就知道了 (37) ssadwlll 2008-07-20 12:44:21
  • 因为覆盖的条件不同，1065值相等时候也算覆盖，而这值相等不算覆盖，见内 (28) taylor_tao 2008-08-12 22:07:24
    • Re:因为覆盖的条件不同，1065值相等时候也算覆盖，而这值相等不算覆盖，见内 (60) lingd 2008-09-15 22:09:07
      • Re:因为覆盖的条件不同，1065值相等时候也算覆盖，而这值相等不算覆盖，见内 (257) wangshn 2009-05-26 21:57:00
        • Re:因为覆盖的条件不同，1065值相等时候也算覆盖，而这值相等不算覆盖，见内 (244) zyz123 2012-07-19 20:25:33
• 好方法！顶！ (7) scaneeling 2009-01-08 20:15:38
• Re:贪心算法和二分思想的实现 (386) humanoid 2013-10-11 11:09:48