#include <stdio.h>
#include <algorithm>



struct Wood
{
	Wood()
	{

	}
	Wood(int _w,int _l):w(_w),l(_l)
	{

	}
	int w,l;
};

int cmp(const void*a,const void*b)
{
	Wood* pa = (Wood*)a;
	Wood* pb = (Wood*)b;
	if( pa->l != pb->l)
		return pa->l > pb->l;
	else
		return pa->w > pb->w;
}

Wood woods[5002];
int longestSQ[5002];

int main()
{
	int n;
	int ncase;
	FILE *file = fopen("data.txt","r");
	fscanf(file,"%d",&ncase);
	//scanf("%d",&ncase);
	while(ncase--)
	{
		fscanf(file,"%d",&n);
		//scanf("%d",&n);
		int i;
		for( i = 0; i < n ;i++)
		{
			//scanf("%d%d",&(woods[i].l),&(woods[i].w) );

			fscanf(file,"%d%d",&(woods[i].l),&(woods[i].w) );
		}
		qsort(woods,n,sizeof(woods[0]),cmp);
		memset(longestSQ,0,sizeof(longestSQ));

		for( i = 0; i < n; i++)
		{
			longestSQ[i] = 1;
		}
		int j;
		int r = 1;//the first one is selected
		for( i = 1; i < n; i++)
		{
			bool t = false;
			for( j = 0 ; j < i ; j++)
			{
				if(woods[j].w <= woods[i].w  && longestSQ[i] < longestSQ[j] + 1)
				{
					longestSQ[i]= longestSQ[j]+1;
					t = true;
				}
			}
			if( !t )
			{
				r++;
			}
			
		}

		
		printf("%d\n",r);

	}
	return 0;
}

• Re:有谁帮我看一下哪里错了 为什么wa 主要思路是 sort + 找不下降子序列个数 (23) hopeztm 2012-02-19 16:17:17