Russian Dolls

Russian Dolls

DP。最長増加部分列。

int main() {
    while (1) {
        vector< pair<int, int> > vp;
        int dp[205];
        int n; cin >> n; if (n == 0) break;
        for (int i = 0; i < n; i++) {
            int h, r; cin >> h >> r;
            vp.push_back(pair<int, int>(h, r));
        }
        int m; cin >> m;
        for (int i = 0; i < m; i++) {
            int h, r; cin >> h >> r;
            vp.push_back(pair<int, int>(h, r));
        }
        sort(vp.begin(), vp.end());
        for (int i = 0; i < vp.size(); i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (vp[j].first < vp[i].first && vp[j].second < vp[i].second) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < vp.size(); i++) {
            res = max(res, dp[i]);
        }
        cout << res << endl;
    }

    return 0;
}