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

char str[maxn];

int a[maxn];

int dp[(<<)];

int main()

{

    cin>>str;

    int L = strlen(str), ans = ;

    for(int i = ; i < L; i++){

        ans ^= (<<(str[i] - 'a'));

        a[i] = ans;

    }

    memset(dp, , sizeof(dp));

    for(int i = ; i < L; i++){

        int ok = ;

        for(int j = ; j < ; j++) if(a[i] ==  || (a[i]^(<<j)) == ) { dp[a[i]] = ; ok = ; break; }

        if(ok) continue;

        for(int j = ; j < ; j++)

            dp[a[i]] = min(dp[a[i]^(<<j)]+, dp[a[i]]);

    }

    cout<<dp[a[L-]]<<endl;

    return ;

}

巴特西

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

最新文章

热门文章