231 – Testing the CATCHER

A Dynamic Programming problem.
A straight-forward application of the Longest Increasing Sub-sequence algorithm.
Caution!

• Insert a new line between data sets.
• The CATCHER can move forward. i.e Longest Non-Decreasing Sub-sequence is required.

C++ implementation:

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

typedef long long int64;

vector<int> missileH;
vector<int> lis;

int main() {
	int caseI = 0, maxLIS;
	// solve
	while (true) {
		// input
		missileH.clear();
		lis.clear();
		for (int h; cin >> h && h != -1; lis.push_back(1))
			missileH.push_back(h);
		if (!missileH.size())
			break;
		// solve
		maxLIS = 1;
		for (int i = 0; i < missileH.size(); ++i) {
			for (int j = 0; j < i; ++j)
				if (missileH[i] <= missileH[j])
					lis[i] = max(1 + lis[j], lis[i]);
			maxLIS = max(maxLIS, lis[i]);
		}
		// output
		if (caseI)
			cout << endl;
		cout << "Test #" << ++caseI << ":" << endl << 
				"  maximum possible interceptions: " << maxLIS << endl;
	}
	return 0;
}