NYoj 16

먼저 정렬하고 dp를 사용하세요

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int MAXN = 1010;
struct Rectangle
{
	int len;
	int wide;
	Rectangle()
	{
		len = 0;
		wide = 0;
	}
};

Rectangle Rec[MAXN];

int MAX(int a, int b)
{
	return a > b ? a : b;
}


int MIN(int a, int b)
{
	return a < b ? a : b;
}

int Cmp(const void *a, const void *b)
{
	Rectangle* aa = (Rectangle *)a;
	Rectangle* bb = (Rectangle *)b;
	return aa->len - bb->len;
}

int main()
{
	int T;
	int n, i, j;
	int dp[MAXN];
	cin>>T;
	while (T--)
	{
		cin>>n;
		int a, b;
		memset(dp, 0, sizeof(dp));
		for (i = 0; i < n; ++i)
		{
			cin>>a>>b;
			Rec[i].len = MAX(a, b);
			Rec[i].wide = MIN(a, b);
			dp[i] = 1;
		}

		qsort(Rec, n, sizeof(Rec[0]), Cmp);

		for (i = 1; i < n; ++i)
		{
			for (j = 0; j < i; ++j)
			{
				if(Rec[i].len > Rec[j].len && Rec[i].wide > Rec[j].wide)
					dp[i] = MAX(dp[i], dp[j] + 1);
			}
		}

		int ans = 0;
		for(i = 0; i < n; ++i)
			if(dp[i] > ans)
				ans = dp[i];
		cout<<ans<<endl;
	}
	return 0;
}