Problem 0157 : Russian Dolls

404 Not Found

メモ化再帰で解ける。DPが思いつかない。nとm別々に与えられるけどひとまとめにする。

自分自身より小さいの一つ見つけて、それが含める最大の数(自分自身含む)を同じように再帰で求める。dfsの引数でメモ化。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int memo[200] = {0};
int h[200] , r[200];
int n,m;

int dfs(int id){
	if(memo[id])return memo[id];
	int ans = 1;
	rep(i,n+m){
		if(h[i] < h[id] && r[i] < r[id])
			ans = max(dfs(i)+1,ans);
	}
	return memo[id] = ans;
}

int main(){
	while(cin >> n , n){
		rep(i,200)memo[i] = 0;
		rep(i,n)cin >> h[i] >> r[i];
		cin >> m;
		rep(i,m)cin >> h[n+i] >> r[n+i];
		int ans = 0;
		rep(i,n+m) ans = max(ans,dfs(i));
		cout << ans << endl;
	}
}

2011/03/24 10:46

思いついた。ていうか再帰でやってることを強引にループで収束させてるだけ。これdpっていえるのか?

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int dp[200] = {0};
int h[200] , r[200];
int n,m;

int main(){
	while(cin >> n , n){
		rep(i,n)cin >> h[i] >> r[i];
		cin >> m;
		rep(i,m)cin >> h[n+i] >> r[n+i];
		int ans = 0;
		rep(i,200)dp[i] = 1;
		rep(x,n+m){
			rep(i,n+m)rep(j,n+m){
				if(h[j] < h[i] && r[j] < r[i]){
					dp[i] = max(dp[j]+1,dp[i]);
				}
			}
		}
		cout << *max_element(dp,dp+n+m) << endl;
	}
}