atcoder 2017Code festival C ——D题 Yet Another Palindrome Partitioning（思维+dp）

题目大意：

把一个字符串s分割成m个串，这m个串满足至多有一种字符出现次数为奇数次，其他均为偶数次，问m的最小值

题解：

首先我们想一下纯暴力怎么做

显然是可以n^2暴力的，然后dp[i]表示分割到i的所用最少的串个数

接下来就是枚举所有可行的j，使得dp[j]转移到dp[i]。

虽然可以暴力找，但是如果使用暴力找，则后续就无法优化了，这里就用到了异或的思想

用一个26位的int数组a[i]表示从1到i的状态，第j位为1代表这个字母出现了奇数次，反之为偶数次。

那么区间[l, r]是否可行，就是a[l]^a[r]的值必须为2的幂次。

有了这个性质，转移依然是n^2的，但是我们可以优化它。

dp[i][x]表示1~i中当前状态为x，分割到i所用最少的串个数。

那么考虑如何更新i+1，首先i+1的状态是固定的，就是a[i]。

所以能更新的就是所有使得y^a[i]是2的幂次的y，dp[i][a[i]] = min(dp[i][a[i]], dp[i-1][y])。

注意异或是可交换，那么只需要枚举2的幂次，然后和a[i]异或，就可以得到y了

于是就这么神奇的做完了！

复杂度O(26*n)

题解很麻烦，但是代码量是很少的。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 100;
char str[maxn];
int a[maxn];
int dp[(1<<26)];
int main()
{
    cin>>str;
    int L = strlen(str), ans = 0;
    for(int i = 0; i < L; i++){
        ans ^= (1<<(str[i] - 'a'));
        a[i] = ans;
    }
    memset(dp, 1, sizeof(dp));
    for(int i = 0; i < L; i++){
        int ok = 0;
        for(int j = 0; j < 26; j++) if(a[i] == 0 || (a[i]^(1<<j)) == 0) { dp[a[i]] = 1; ok = 1; break; }
        if(ok) continue;
        for(int j = 0; j < 26; j++)
            dp[a[i]] = min(dp[a[i]^(1<<j)]+1, dp[a[i]]);
    }
    cout<<dp[a[L-1]]<<endl;
    return 0;
}