[USACO 2007 Jan B]The Bale Tower

NC25039. [USACO 2007 Jan B]The Bale Tower

描述

Always bored with cud-chewing, the cows have invented a new game. One cow retrieves a set of N (3 <= N <= 20) hay bales from the shed each of which is one unit high. Each bale also has some unique width and unique breadth.
A second cow tries to choose a set of bales to make the tallest stack of bales in which each bale can be placed only on a bale whose own width and breadth are smaller than the width and breadth of the bale below. Bales can not be rotated to interchange the width and breadth.
Help the cows determine the highest achievable tower that can be legally built form a set of bales.

输入描述

* Line 1: A single integer, N
* Lines 2..N+1: Each line describes a bale with two space-separated integers,respectively the width and breadth

输出描述

* Line 1: The height of the tallest possible tower that can legally be built from the bales.

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2019-12-14 11:35:42

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
struct ljy{
	int a,b;
}f[30];
int dis[30];
bool operator <(const ljy &x,const ljy &y){
	return x.a<y.a||x.a==y.a&&x.b>y.b;
}
int main(){
	int n,ans=-2e9;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>f[i].a>>f[i].b;
	sort(f+1,f+n+1);
	for(int i=1;i<=n;i++){
		dis[i]=1;
		for(int j=1;j<i;j++)
		if(f[i].b>f[j].b)dis[i]=max(dis[i],dis[j]+1);
	}
	for(int i=1;i<=n;i++)
	ans=max(ans,dis[i]);
	cout<<ans<<"\n";
	return 0; 
}