SRM499 Div2 Hard(950) PalindromeGame
AA'とBB'が回文ならば、ABB'A'もBAA'B'も回文となる。回文になる組み合わせを点数の高いものから貪欲に取っていく。その後、単体で回文になる文字列があれば中心に加える。中心を先に選ぶと、{aba, aba}のような入力で間違える。
#include <string> #include <vector> #include <algorithm> using namespace std; struct C { string f; int b; C(string f_,int b_):f(f_),b(b_){} bool operator<(const C&a)const{return b>a.b;}; }; string rev(string s) { return string(s.rbegin(),s.rend()); } class PalindromeGame{public: int getMaximum( vector <string> front, vector <int> back ) { int N = (int)front.size(); vector<C> c; for ( int i=0; i<N; i++ ) c.push_back( C(front[i],back[i]) ); sort( c.begin(), c.end() ); int ans = 0; vector<bool> used(N); for ( int i=0; i<N; i++ ) if ( !used[i] ) { for ( int j=i+1; j<N; j++ ) if ( !used[j] && c[i].f==rev(c[j].f) ) { ans += c[i].b + c[j].b; used[i] = used[j] = true; break; } } for ( int i=0; i<N; i++ ) if ( !used[i] && c[i].f==rev(c[i].f) ) { ans += c[i].b; used[i] = true; break; } return ans; }};