学步园

给定N个人的身高和体重，然后叠罗汉。规则是：每个人踩在另一个人的肩膀上，上面人的身高和体重都要低于下面的人。实现一个方法计算N个人最多可以叠多少人。

例子：

输入(height, weight)：(65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

输出：6 （从上到下是：(56,
90) (60,95) (65,100) (68,110) (70,150) (75,190)）

思路：

可以先根据身高排序（身高相同时按体重排序），这样就满足了一个条件，然后求体重的序列的最长递增子序列，这样就满足了第二个条件。即问题转换成了经典的LIS问题。

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

struct person
{
	int he;
	int we;
};

bool cmp(person p1, person p2)
{
	if (p1.he == p2.he)
		return p1.we < p2.we;
	else
		return p1.he < p2.he;
}

int LNP(const vector<person>& pvec)
{
	if (pvec.size() <= 1)
		return pvec.size();
	vector<int> ivec;
	sort(pvec.begin(), pvec.end(), cmp);
	ivec.push_back(pvec[0].we);
	for (int i = 1; i < pvec.size(); ++i)
	{
		if (pvec[i].we > ivec.back())
			ivec.push_back(pvec[i].we);
		else
		{
			int left = 0, right = ivec.size() - 1;
			while (left <= right)
			{
				int mid = left + ((right - left) >> 1);
				if (ivec[mid] <= pvec[i].we)
					left = mid + 1;
				else
					right = mid - 1;
			}
			ivec[left] = pvec[i].we;
		}
	}
	return ivec.size();
}