テキトーなメモ帳

テキトーなメモ帳

AOJ:0157 Russian Dolls

動的計画法かなあ・・・

#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

static const double eps = 10e-8;

class mycmp{
public:
	bool operator()(const P p1, const P p2){
		if(p1.first < p2.first) return true;
		else if(p1.second < p2.second) return true;
		else false;
	}
};

int main(){
	int n;

	while(~scanf("%d",&n)){
		if(n==0) break;
		vector<P> dolls;

		for(int i=0;i<n;i++){
			int h,r;
			scanf("%d %d",&h,&r);
			dolls.push_back(P(h,r));
		}

		int m;
		scanf("%d",&m);
		for(int i=0;i<m;i++){
			int h,r;
			scanf("%d %d",&h,&r);
			dolls.push_back(P(h,r));
		}


		sort(dolls.begin(),dolls.end());

		int* dp = new int[n+m];
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n+m;i++) dp[i] = 1;

		for(int i=0;i<dolls.size();i++){
			for(int j=0;j<dolls.size();j++){
				if(dolls[j].first < dolls[i].first
					&& dolls[j].second < dolls[i].second){
						dp[i] = max(dp[i],dp[j] + 1);
				}
			}
		}

		cout << dp[dolls.size()-1] << endl;
		delete[] dp;
	}
}