読者です 読者をやめる 読者になる 読者になる

AOJ 0157 Russian Dolls

C/C++ Algorithms DP AOJ

問題

(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]だけでやろうとしたけど