マトリョーシカ

パソコン甲子園2007予選問題

問題 マトリョーシカ

概要

高さが h 半径が r の筒状の人形が n + m 個与えられる。高さ h 半径 r の人形は x < h かつ y < r を満たす高さ x 半径 y の人形を含むことができる。これらの人形の中から複数選んで k 個の人形の入れ子（マトリョーシカ）を作るとき、k の最大値を求めよ。

解法

高さ（または半径）で全ての人形をソートします。ソートした人形に対して半径（または高さ）についての最長増加部分列の長さを動的計画法により求めます。


サインプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 200
005 
006 class Doll{
007     public:
008     int h, r;
009     Doll(){}
010     Doll( int h, int r ): h(h), r(r){}
011     
012     bool operator < ( const Doll &d ) const {
013         if ( r == d.r ) return h < d.h;
014         else return r < d.r;
015     }
016 };
017 
018 Doll dolls[MAX+1];
019 int size;
020 
021 int lis(){
022     int T[MAX+1];
023     T[0] = 0;
024     dolls[0] = Doll( 0, 0 );
025     for ( int i = 1; i <= size; i++ ){
026         int maxi = 0;
027         for ( int j = 0; j <= i - 1; j++ ){
028             if ( T[j] > T[maxi] &&
029             dolls[j].h < dolls[i].h && dolls[j].r < dolls[i].r ){
030                 maxi = j;
031             }
032         }
033         T[i] = T[maxi] + 1;
034     }
035     
036     int maxv = 0;
037     for ( int i = 1; i <= size; i++ ) maxv = max( maxv, T[i] );
038     
039     return maxv;
040 }
041 
042 bool input(){
043     int n, m, h, r;
044     cin >> n;
045     if ( n == 0 ) return false;
046     
047     dolls[0] = Doll(0, 0);
048     
049     for ( int i = 1; i <= n; i++ ){
050         cin >> h >> r;
051         dolls[i] = Doll( h, r );
052     }
053     cin >> m; size = n + m;
054     for ( int i = n + 1; i <= size; i++ ){
055         cin >> h >> r;
056         dolls[i] = Doll( h, r );
057     }
058     return true;
059 }
060 
061 int main(){
062     while(input()){
063         sort( dolls, dolls + size + 1);
064         cout << lis() << endl;
065     }
066     return 0;
067 }