マトリョーシカ
2007.10.04 15:13 パソコン甲子園 2007
パソコン甲子園2007予選問題
問題 マトリョーシカ
概要
高さが h 半径が r の筒状の人形が n + m 個与えられる。高さ h 半径 r の人形は x < h かつ y < r を満たす高さ x 半径 y の人形を含むことができる。これらの人形の中から複数選んで k 個の人形の入れ子（マトリョーシカ）を作るとき、k の最大値を求めよ。
解法
高さ（または半径）で全ての人形をソートします。ソートした人形に対して半径（または高さ）についての最長増加部分列の長さを動的計画法により求めます。
サインプルプログラム
問題 マトリョーシカ
概要
高さが 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |