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