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; }