学步园

#include <iostream>
using namespace std;

struct person
{
	int w, h;
};

const int maxn = 100;
int d[maxn] = {0};

bool cmp(person a, person b)
{
	if(a.h == b.h)
		return a.w < b.w;
	return a.h < b.h;
}

int dp(person a[], int n)
{
	int k = 0, len = 1;
	
	for(int i = 0; i < n; ++i)
	{
		d[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(a[i].w > a[j].w && d[j] + 1 > d[i])
				d[i] = d[j] + 1;
		}
		if(len < d[i])
				len = d[i];
	}
	
	return len;
}

int main(void)
{
	freopen("1.txt", "r", stdin);
	
	person  a[maxn];
	int i = 0, j = 0;

	//while(scanf("%d", &h[i])!=EOF)
	while(cin >> a[i].h)
	{
		cin >> a[i].w;
		i++;
	}

	sort(a, a+i, cmp);

	cout << dp(a, i) << endl;

	return 0;
}

附测试用例 1.txt

65 100
70 150
56 90
75 190
60 95
68 110.

好题重写一遍加深印象

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct person
{
	int w, h;
}person;

const int maxn = 255;
person pt[maxn];

bool cmp(person a, person b)
{
	if(a.w == b.w)
		return a.h < b.h;	
	else
		return a.w < b.w;
}

int hew[maxn] = {
	0
};

void lis(person a[], int len)
{
	for(int i = 0; i < len; ++i)
	{
		hew[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(a[i].h > a[j].h)
			{
				hew[i] = hew[i] < hew[j] + 1 ? hew[j] + 1 : hew[i];
			}
		}
	}
}

int main(void)
{
	freopen("1.txt", "r", stdin);
	
	int N, i = 0;
	cin >> N;
	while(N--)
	{
		cin >>pt[i++].w >> pt[i].h;	//学到一点，cin的读入也是从右至坐的，所以i++放最左边 
	}

	sort(pt, pt + i, cmp);
	
	lis(pt, i);
	
	cout << hew[i-1] << endl;
	
	return 0;
}