CC150 11.7

11_7.cpp

/* CC150 11.7 */
// compute the largest possible people tower, givin (ht, wt)

#include <iostream>
#include <vector>

using namespace std;

class Person {
public:
	Person() : height(0), weight(0) {}
	Person(int h, int w) : height(h), weight(w) {}
	int getHt() { return height; }
	int getWt() { return weight; }
	bool isSmallerThan(Person p) { return height < p.getHt() && weight < p.getWt(); } // strictly smaller
private:
	int height, weight;
};

void buildTower(vector<Person> people, int index, vector<vector<int>> &buff)
{
	if (!buff[index].empty())
		return;
	int hmaxIndex = 0;
	for (int i = 0; i != people.size(); ++i) {
		if (i == index)
			continue;
		if (people[i].isSmallerThan(people[index])) { // Person i can be placed on top of current person
			buildTower(people, i, buff); // build sub-tower on Person i
			if (buff[i].size() > buff[hmaxIndex].size()) // keep track of index of the largest sub-tower
				hmaxIndex = i;
		}
	}
	buff[index] = buff[hmaxIndex]; // copy the largest sub-tower and append current person at the end
	buff[index].push_back(index);
}

vector<int> buildTower(vector<Person> people)
{
	vector<vector<int>> buff(people.size());
	int hmaxIndex = 0;
	for (int i = 0; i != people.size(); ++i) {
		buildTower(people, i, buff);
		if (buff[i].size() > buff[hmaxIndex].size())
			hmaxIndex = i;
	}
	return buff[hmaxIndex];
}

int main()
{
	vector<Person> people;
	int ht, wt;
	while (cin >> ht >> wt)
		people.push_back(Person(ht, wt));
	vector<int> tower = buildTower(people);
	cout << "The longest tower is length " << tower.size()
		<< " and includes from top to bottom: " << endl;
	for (auto p : tower)
		cout << "(" << people[p].getHt() << ", " << people[p].getWt() << ") ";
	cout << endl;
	return 0;
}

output

65 100
70 150
56 90
75 190
60 95
68 110
^Z
The longest tower is length 6 and includes from top to bottom:
(56, 90) (60, 95) (65, 100) (68, 110) (70, 150) (75, 190)