最坏的情况是我在侥幸在zju上过关了，否则，　还会有什么原因呢？
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#define MAXN 5001
struct Stick {
	int l, w;	
}a[MAXN];
int n;
int cmp( const void * a, const void * b)
{
	return ((const Stick *)a)->l - ((const Stick *)b)->l;	
}
int d[MAXN];
// longest increasing subsequence
int lis() 
{
	int seg = 0; 
	int max, sec;
	for(int i=1; i<=n; ++i)
	{
		max = -1;
		for(int j=0; j<seg; ++j) if( a[i].w >= d[j] && max < d[j] ) { max = d[j]; sec = j; }
		if( max == -1 ) d[seg++] = a[i].w;
		else d[sec] = a[i].w;
	}
	return seg;
}

int main()
{
	int t; scanf("%d", &t);
	while( t-- )
	{
		scanf("%d", &n);
		for(int i=1; i<=n; ++i) scanf("%d%d", &a[i].l, &a[i].w);
		qsort( &a[1], n, sizeof(Stick), cmp );
		printf( "%d\n", lis() );
	}
	return 0;
}

• ac了，主要是qsort的判定条件写的太简单，　只要加上在len相等情况下处理weight就ok (894) navyakula 2006-02-04 01:19:37
  • Re:ac了，主要是qsort的判定条件写的太简单，　只要加上在len相等情况下处理weight就ok (27) KosonLau 2007-04-18 02:43:00
    • Re:ac了，主要是qsort的判定条件写的太简单，　只要加上在len相等情况下处理weight就ok (20) yezizhe 2007-07-30 15:45:16