UVa 418 - Molecules
http://uva.onlinejudge.org/external/4/418.html
問題概要
可能な限り大きいスーパーモルキュールを作ろう。
コード
#include<iostream> #include<string> #include<vector> #include<cassert> #include<algorithm> #define LEN 12 #define RNG 11 using namespace std; int SubMolecules( const vector< string > &moles ){ int ret = 0; for(int a = 1; a < RNG; ++a){ for(int b = 1; b < RNG; ++b){ if( moles[0][a] == moles[1][b] ){ for(int bc = b+2; bc < RNG; ++bc){ for(int c = 1; c < RNG; ++c){ if( moles[1][bc] == moles[2][c] ){ int da_max = min( RNG - c, RNG - a ); for(int da = 2; da < da_max; ++da){ for(int d = 1; d < RNG - (bc-b); ++d){ if( moles[0][a+da] == moles[3][d] && moles[3][d + (bc-b)] == moles[2][(a+da) - (a-c)] ){ int ad_len = da - 1; int bc_len = bc - b - 1; ret = max( ret, bc_len * ad_len ); } } } } } } } } } return ret; } int Molecules( const vector<string> &moles ){ int ret = 0; int a[] = {0,1,2,3}; ret = max( ret, SubMolecules( moles ) ); while( next_permutation( a, a+4 ) ){ vector< string > perm_mole(moles.begin(), moles.end()); for(int i = 0 ; i < 4; ++i){ perm_mole[i] = moles[ a[i] ]; } ret = max( ret, SubMolecules( perm_mole ) ); } return ret; } int main(){ while(true){ vector< string > moles; for(int i = 0; i < 4; ++i){ string s; cin >> s; moles.push_back( s ); if( moles[i].find('Q') != string::npos ) return 0; } cout << Molecules( moles ) << endl; } return 0; }
コードの内容
全探索する。並び替えて組み合わせられるやつを順次探していく。