メモ化再帰で解ける。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; } }