UVa1196

UVa1196

LIS。O(N^2) でも間に合うらしい。
何も考えずにメモ化したら通った。

#include <iostream>
#include <algorithm>

#include <vector>
using namespace std;

vector< pair<int , int> > b;

const int M = 10000 + 1;
int memo[M];

int rec(int curr)
{
  int &ret = memo[curr];
  if (ret != -1) return ret;

  int mx = 0;
  for (int next = curr + 1; next < (int)b.size(); ++next) {
    if (b[curr].first >= b[next].first &&
        b[curr].second >= b[next].second) {
      mx = max(mx, rec(next) + 1);
    }
  }

  return ret = mx;
}

int main(void)
{
  int n;
  while (cin >> n && n) {
    b.resize(n);
    for (int i = 0; i < n; ++i) {
      cin >> b[i].first >> b[i].second;
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());

    fill(memo, memo + M, -1);   
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      mx = max(mx, rec(i));
    }
    cout << mx+1 << endl;
  }
  cout << '*' << endl;
  return 0;
}