AOJ 0157 Russian Dolls
問題
(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157)
解法
DPで解きます。ソートした後最長増加部分列を求めます。
コード
int n, m; vector<pi>s; int dp[1024]; int main(){ while(scanf("%d", &n) && n){ s.clear(); int h, r; rep(i, n){ scanf("%d%d", &h, &r); s.push_back(MP(h, r)); } scanf("%d", &m); rep(i, m){ scanf("%d%d", &h, &r); s.push_back(MP(h, r)); } sort(s.begin(), s.end()); memset(dp, 0, sizeof(dp)); int res = 0; rep(i, s.size()){ dp[i] = 1; rep(j, i) if(s[j].F < s[i].F && s[j].S < s[i].S){ dp[i] = max(dp[i], dp[j] + 1); } res = max(res, dp[i]); } printf("%d\n", res); } return 0; }
構造体で比較演算子定義してs[j]<s[i]だけでやろうとしたけど