本文共 873 字,大约阅读时间需要 2 分钟。
题意:
给出一个字符串,最少需要多少次拆分得到的子串都是合法的,合法的定义是改变字符串顺序能得到一个回文串。
解题思路:
容易想到的是一个合法的字符串的26个字母最多只能一个字母出现次数为奇数,用26位二进制数(mask)表示,1表示奇数的话,只有能整除2的和0是合法的。
dp想法是每个状态减去一个合法串然后转移过来,但是显然不能for一下,这时候就利用下上面的mask。
用mask表示前缀串里字母的奇偶性,转移就是,在当前的字符串下,砍掉一个合法的子串,就是可以转移过来的状态,砍掉一个有一个字母是奇数的子串等价于maks^(1<<j),j是26个字母,砍掉一个全是偶数的子串就等价于mask自己(mask^0=mask)。用一个map记录mask对应的值就好。
代码:
#includeusing namespace std;const int maxn=2e5+5;char str[maxn];unordered_map mi;int get(int x){ if(mi.count(x)) { return mi[x]; } return maxn;}void add(int x, int val){ if(!mi.count(x)) { mi[x]=val; } else mi[x]=min(mi[x], val);}int main(){ scanf("%s", str); int i, j; int dp=0, mask=0; for(i=0; str[i]; i++) { add(mask, dp); mask^=1<<(str[i]-'a'); dp=get(mask)+1; for(j=0; j<26; j++) { dp=min(dp, get(mask^(1<
转载地址:http://goywb.baihongyu.com/