SRM 439 Div1 Medium PalindromePhrases

問題概要

フレーズが回文であるとは、空白文字を除いた文字列が回文であることである。
単語がいくつか与えられるとき、
それらを、それぞれ一度まで使ってできるフレーズのうち、回文であるものの総数を求めよ。
フレーズは単語をスペースで区切って並べて作る。

二つのフレーズは文字が同じでもスペースの位置が異なれば異なるものとする。

制約条件

単語の数≦13,
各単語の長さ≦13
各単語は全て異なる

方針

回文を両端から決定していく。
まだ使っていない単語の集合と、回文からはみ出ている部分を決めると、
そこまでの部分の状態が同一視できるので、場合の数が掛け算で求められる。

dp[単語の集合][はみでた文字]のようなDPができる。
……うまく説明しにくいorz
ちゃんと言語化できないと似たような問題解けないような気がする。。。

ソースコード

typedef pair<string,string> ps;
vector<map<ps,ll> >dp;

class PalindromePhrases {
  public:
  long long getAmount(vector <string> words) {

    int n=words.size();
    dp.clear(); dp.resize(1<<n);
    dp[(1<<n)-1][ps("","")]=1;
    //dp[まだ使える単語のビット][左側からはみでる文字,右側からはみでる文字] = その場合の数
    
    ll ans=0;
    for(int mask=(1<<n)-1;mask>=0;mask--)fr(j,dp[mask])rep(k,n)if(mask&1<<k){
        string l=j->first.first,r=j->first.second,s; bool kaibun=1;
        if(l.empty())l=words[k]; else r=words[k];
        
        int len=0;
        for(;len<l.size()&&len<r.size();len++)if(l[len]!=r[r.size()-len-1])goto FAIL;
        if(l.size()>=r.size())l=l.substr(len), r="";
        else r=r.substr(0,r.size()-len), l="";

        s=r.empty()?l:r;
        for(int p=0,q=(int)s.size()-1;p<q;p++,q--)if(s[p]!=s[q])kaibun=0;
        if(kaibun)ans+=j->second; //はみでた部分が回文になっていたらそこまでが回文なので答えに足す
        dp[mask^1<<k][mp(l,r)]+=j->second;
      FAIL:;
    }
    return ans;
  }
};