[AtCoder Code Festival Qual C] D - Yet Another Palindrome Partitioning DP

Prob.

给一个字符串。求一个最小的划分使得每一个子串重排后可以构成一个回文串。

Sol.

前三题太简单，后三题都不会做，难受。
把每一个字符的奇偶性压着存进 DP ，注意到 $ dp[i][S] = \min_{j < i} \\{dp[j][S], dp[j][S\oplus(2^k)] + 1\\} $。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100, maxm = 1 << 26, INF = 0x3f3f3f3f;
int dp[maxm + 5];
char s[maxn];
inline int idx(char c){return c - 'a';}
int main()
{
    scanf("%s", &s);
    int len = strlen(s);
    memset(dp, INF, sizeof dp); dp[0] = 0;
    int tmp = 0;
    for(int i = 0; i < len; ++i)
    {
        tmp ^= (1 << idx(s[i]));
        for(int j = 0; j < 26; ++j) dp[tmp] = min(dp[tmp], dp[tmp^(1 << j)] + 1);
    }
    printf("%d\n", max(1, dp[tmp]));
    return 0;
}