POJ 3636 俄罗斯Nested Dolls 贪心二分 动态规划

首先要区分#include <cstdlib> 中的qsort与C++ STLalgorithm中的sort，后者只有三个参数且比较函数写法较简单些

类似于POJ 1065,差异有二，其一是排序方式下降，其二是要求下降且不相等

但是用常规的贪心会超时,用二分优化后不超时，注意对l递增排，对w递减排

// 类似于POJ 1065,差异有二，其一是排序方式下降，其二是要求下降且不相等
// 上面这种解法会超时,用二分优化后不超时，注意对l递增排，对w递减排
#include <iostream>  
#include <cstdio>
#include <cstdlib>  
using namespace std;  
typedef struct stick{  
    int l;  
    int w;  
}stick;  
int cmp(const void *a,const void *b)  
{  
    if((*(stick *)a).l!=(*(stick *)b).l)  
    {  
        return (*(stick *)a).l - (*(stick *)b).l;  
    }  
    else  
    {  
        return (*(stick *)b).w - (*(stick *)a).w;  
    }  
} 
int main(){  
    int n,m,i; 
	int T[20010],len=0,r,l,mid;
    stick p[20005];  
	scanf("%d",&n);
    while(n--){  
        len = 0;  
        scanf("%d",&m); 
        for (i = 0;i < m;i++)  
        {  
			 scanf("%d%d",&p[i].l,&p[i].w);
        }  
        qsort(p,m,sizeof(stick),cmp);  
		memset(T,0,sizeof(T));
		for( i=0;i<m;i++)
		{
			l=0;
			r=len;
			while(l<r)//用二分进行优化
			{
				mid=(l+r)/2;
				if(T[mid]>=p[i].w) l=mid+1;
				else r=mid;
			}
			if(len==l) len++;
			T[l]=p[i].w;
		}
		printf("%d/n",len);
    }  
    return 0;  
}