D - Yet Another Palindrome Partitioning

https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_d

思考

回文の条件は奇数個のアルファベットが高々1つ

アルファベットはbitで持てる

いくつかの区間に分割するdpか、左から貪欲に取ればよさそう

貪欲は駄目だった

だから分割dp

dp[i] := iまでを分割するときの最小として

あるiについてi>jなるjで、j~iの区間が回文条件を満たしており、dp[j]が最小となる物が見つけられれば遷移できそう

zero sum rangesを連想した　

各アルファベットの差分で奇数となる物が高々一つならいい

つまりアルファベットの偶奇の累積和を取ればいい（bitで持てる）

bitで持てるのでbest[m] :=  累積(01)がmとなる場所の内、最小の分割数　とできる

遷移は現在地点の累積をmとして、偶奇が異なるbitを26通り試してやればいい

類題

https://atcoder.jp/contests/agc023/tasks/agc023_a

https://atcoder.jp/contests/agc031/tasks/agc031_b

https://atcoder.jp/contests/code-festival-2017-qualc/submissions/4799781

map<int,int> bes;
void solve() {
    string s = sin();
    n = sz(s);
    minu(s, 'a');
    //0  indexで考えられる
    bes[0] = 0;
    int m = 0;
    int res = 0;//一番最後が答え
    rep(i, n) {
        m ^= bit(s[i]);
        if (!bes.count(m))bes[m] = inf;
        int lv = inf;
        //全て偶数
        chmi(lv, bes[m]);
        //bが奇数
        rep(b, 26) {
            int tm = m ^bit(b);
            if (!bes.count(tm))continue;
            chmi(lv, bes[tm]);
        }
        if (i == n - 1)res = lv + 1;//右端なら必ず取る
        else chmi(bes[m], lv + 1);
    }

    cout << res << endl;
}