> 最坏的情况是我在侥幸在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;
> }

• 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