AOJ_0157: Russian Dolls

Russian Dolls | Aizu Online Judge

DPの練習。最長増加部分列問題。 昨日の問題↓rainline.hatenadiary.jp は数列の並び順が完全に固定されてたけれど、今日の問題はもともと数列ではなくその順番は可換なのでループの回し方が異なった。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector< pair<int,int> > doll;
int dp[200];
int n,m,tmp1,tmp2;

int main(){
  while(cin>>n && n){
    for(int i=0;i<n;i++){
      cin>>tmp1>>tmp2;
      doll.push_back(make_pair(tmp1,tmp2));
    }
    cin>>m;
    for(int i=0;i<m;i++){
      cin>>tmp1>>tmp2;
      doll.push_back(make_pair(tmp1,tmp2));
    }

    sort(doll.begin(),doll.end());

    int ans=0;

    for(int i=0;i<n+m;i++){
      dp[i]=1;
      for(int j=0;j<n+m;j++){
        if(doll[i].first>doll[j].first && doll[i].second>doll[j].second){
          dp[i]=max(dp[i],dp[j]+1);
        }
      }
      ans=max(ans,dp[i]);
    }

    cout<<ans<<endl;

    while(doll.size()) doll.pop_back();
    memset(dp,0,sizeof(dp));
  }
  return 0;
}