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