SRM499 Div2 Hard(950) PalindromeGame

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;
}};