SRM 499 Div2 Hard PalindromeGame

問題

n枚のカードがあり、表には単語、裏には数字が書かれている。
それぞれのカードに書かれている単語の文字数は全て等しい。

これらのカードのうちいくつかを並べて回文を作るとき、
裏にかかれている数字の和を最大にしたい。そのような和の最大値を求めよ。

回文が作れないときは0を返せ。

制約条件

n≦50

回文の問題苦手だよなーと思ったら正解者かなり多い問題なのにやはりハマったorz

方針

単語の文字数は全て同じ。
したがって、回文の両端に相当するカードから2枚ずつ順々に決定していけばいい。

あるカードに対応するカードが複数枚ある可能性がある（abc,abc,cbaみたいに）ので、
点数の高いカードからGreedyに使うようにする。

2枚ずつカードを選び終わったら、中央に1枚カードが挟まる（1枚のカードがそれだけで回文になっている）可能性を考える。
これも複数候補がある場合、もっとも数字の大きいカードを使えばよい。

ソースコード

class PalindromeGame {
	public:
	int getMaximum(vector <string> front, vector <int> back) 
	{
		int n=front.size(), ans=0;
		vector<pair<int,string> > v;
		rep(i,n)v.pb(mp(-back[i], front[i])); sort(all(v));
		rep(i,n)front[i]=v[i].second, back[i]=-v[i].first;
		
		rep(i,n)if(front[i]!=""){
			reverse(all(front[i]));
			rep(j,i)if(front[i]==front[j]){
				ans+=back[i]+back[j];
				front[i]=front[j]=""; break;
			}
			reverse(all(front[i]));
		}
		
		rep(i,n)if(front[i]!=""){
			string r=front[i]; reverse(all(r));
			if(r==front[i]){
				ans+=back[i];
				break;
			}
		}
		return ans;
	}
};