0157-Russian Dolls

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0157&lang=jp
メモ化探索で十分終わる。

int DP[1002][1002];
struct doll{
	int r;
	int h;
};
doll data[200];
int Count;
int n,m;
int slove(int r,int h){
	if(DP[r][h]>=0) return DP[r][h];
	int res=0;
	for(int i=0;i<Count;i++){
		if(data[i].r<r&&data[i].h<h){
			res=max(res,slove(data[i].r,data[i].h)+1);
		}
	}
	return DP[r][h]=res;
}
int main(){
	for(;;){
		scanf("%d",&n);
		for(int i=0;i<1002;i++){
			for(int j=0;j<1002;j++){
				DP[i][j]=-1;
			}
		}
		if(n==0)return 0;
		for(int i=0;i<n;i++){
			scanf("%d%d",&data[i].h,&data[i].r);
		}
		scanf("%d",&m);
		for(int i=n;i<n+m;i++){
			scanf("%d%d",&data[i].h,&data[i].r);
		}
		Count=n+m;
		printf("%d\n",slove(1001,1001));
		fflush(stdout);
	}

	return 0;
}