/**
 贪心版
 */
/*
#include <iostream>
#define MAX_N 5005

using namespace std;

int input[MAX_N + 1][2];
int n;
int caseNum;
bool used[MAX_N + 1];

int cmp(int pos1, int pos2)
{
	if(input[pos1][0] < input[pos2][0])
		return -1;
	if(input[pos1][0] > input[pos2][0])
		return 1;
	return input[pos1][1] - input[pos2][1];
}

void swap(int pos1, int pos2)
{
	int tempV1 = input[pos2][0];
	int tempV2 = input[pos2][1];

	input[pos2][0] = input[pos1][0];
	input[pos2][1] = input[pos1][1];

	input[pos1][0] = tempV1;
	input[pos1][1] = tempV2;
}

void fastSort(int start, int end)
{
	if(start < end)
	{
		int posS = start, posE = end + 1;
		int curPos = start;
		while(true)
		{
			while(cmp(curPos, ++posS) > 0 && posS < end);
			while(cmp(curPos, --posE) < 0 && posE > start);
			if(posS < posE)
				swap(posS, posE);
			else
				break;
		}
		swap(curPos, posE);
		fastSort(start, posE - 1);
		fastSort(posE + 1, end);
	}
}
int main()
{
	int i, j;
	cin>>caseNum;
	while(caseNum--)
	{
		cin>>n;
		for(i = 1; i <= n; i++)
		{
			cin>>input[i][0]>>input[i][1];
			used[i] = false;
		}
		fastSort(1, n);
		int total = 0;
		
		
		int first;
		for(i = 1; i <= n; i++)
		{
			if(!used[i])
			{
				first = i;
				used[i] = true;
				total++;
			
				for(j = i + 1; j <= n; j++)
				{
					if(!used[j] && input[first][1] <= input[j][1])
					{
						used[j] = true;
						first = j;
					}
				}
			}
		}
		cout<<total<<endl;
	}
	return 0;
}

  */


/**
 动态规划版本，利用动态规划求
 */
#include <iostream>
#define MAX_N 5005

using namespace std;

int input[MAX_N + 1][2];
int n;
int caseNum;
bool used[MAX_N + 1];
int curVal[MAX_N + 1];

int cmp(int pos1, int pos2)
{
	if(input[pos1][0] < input[pos2][0])
		return -1;
	if(input[pos1][0] > input[pos2][0])
		return 1;
	return input[pos1][1] - input[pos2][1];
}

void swap(int pos1, int pos2)
{
	int tempV1 = input[pos2][0];
	int tempV2 = input[pos2][1];

	input[pos2][0] = input[pos1][0];
	input[pos2][1] = input[pos1][1];

	input[pos1][0] = tempV1;
	input[pos1][1] = tempV2;
}

void fastSort(int start, int end)
{
	if(start < end)
	{
		int posS = start, posE = end + 1;
		int curPos = start;
		while(true)
		{
			while(cmp(curPos, ++posS) > 0 && posS < end);
			while(cmp(curPos, --posE) < 0 && posE > start);
			if(posS < posE)
				swap(posS, posE);
			else
				break;
		}

		swap(curPos, posE);
		fastSort(start, posE - 1);
		fastSort(posE + 1, end);
	}
}
int main()
{
	int i, j;
	cin>>caseNum;
	while(caseNum--)
	{
		cin>>n;
		for(i = 1; i <= n; i++)
		{
			cin>>input[i][0]>>input[i][1];
			used[i] = false;
		}
		fastSort(1, n);
		
		memset(curVal, 0, sizeof(curVal));
		curVal[1] = 1;
		int maxVal = -2;
		for(i = 2; i <= n; i++)
		{
			int curMax = 1;
							
			for(j = 1; j <= i - 1; j++)
			{
				if(input[i][0] < input[j][0] || input[i][1] < input[j][1])
					if(curVal[j] + 1 > curMax)
						curMax = curVal[j] + 1;
			}
			curVal[i] = curMax;
			if(curMax > maxVal)
				maxVal = curMax;
			
		}

		cout<<maxVal<<endl;
	}
	return 0;
}

• Re:贴两个都AC的版本的代码，一个贪心，一个动态规划 (7) moment1 2009-08-16 17:21:57