比賽時(shí)候沒(méi)做出來(lái)，現(xiàn)在無(wú)法系統(tǒng)測(cè)試，算法看起來(lái)似乎是沒(méi)問(wèn)題的。
簡(jiǎn)要思想就是一層層生成所有子串，然后計(jì)算這些子串轉(zhuǎn)換成同一字符串所需要的最小轉(zhuǎn)換次數(shù)。
用函數(shù)min_to_make_equal來(lái)生成：將一個(gè)vector<string>中的所有字符串轉(zhuǎn)換成同一個(gè)字符串，所需要改變的最小字符數(shù)。對(duì)于last數(shù)組中的每一個(gè)字符串，將這個(gè)字符串分兩半，后半部翻轉(zhuǎn)。計(jì)算這些字符串轉(zhuǎn)換成同一個(gè)字符串所需要的最小改變次數(shù)，如果這個(gè)次數(shù)小于等于m，說(shuō)明我們可以在m次將它變成回文。計(jì)數(shù)加1。
注意如果字符串長(zhǎng)度為奇數(shù)，我們還要先計(jì)算一下將每個(gè)中間字符變成統(tǒng)一字符所需要的轉(zhuǎn)換次數(shù)，用m減去它。
#include?<iostream>
#include?<sstream>
#include?<vector>
#include?<string>
#include?<algorithm>
using?namespace?std;
int?cnt[51][26];
???class?MaximumPalindromeScore
??????????????{?
??????????????public:?
??????????????int?maximize(string?word,?int?m)?
??????????????????{
??????????????????vector<string>last;
??????????????????last.push_back(word);
??????????????????
??????????????????int?res?=?0;
??????????????????int?i;
??????????????????while(true){
??????????????????????//如果是串的長(zhǎng)度為奇數(shù)，m減去"將中間字符變成統(tǒng)一字符需要的轉(zhuǎn)換次數(shù)"
??????????????????????if(last[0].size()%2==1){
??????????????????????????vector<string>?mid;
??????????????????????????for(i=0;i<last.size();++i){
????????????????????????????mid.push_back(string(1,last[i][last[i].size()/2]));
??????????????????????????}
??????????????????????????m-=min_to_make_equal(mid);
??????????????????????}
??????????????????????
??????????????????????vector<string>?tmp;
??????????????????????//將每個(gè)字符串分割成兩個(gè)子串，前半部不變，后半部翻轉(zhuǎn)
??????????????????????//如果在這一層次上仍滿(mǎn)足回文性質(zhì)，則這些字符串應(yīng)該能夠轉(zhuǎn)換成相同的字符串
??????????????????????for(i=0;i<last.size();++i){
??????????????????????????int?n?=?last[i].size();
????????????????????????string?s1?=?last[i].substr(0,n/2);
????????????????????????string?s2?=?last[i].substr(n-n/2,n/2);
????????????????????????reverse(s2.begin(),s2.end());
????????????????????????tmp.push_back(s1);
????????????????????????tmp.push_back(s2);
??????????????????????}
??????????????????????if(min_to_make_equal(tmp)<=m)
??????????????????????????res++;
??????????????????????else?
???????????????????????????break;
??????????????????????//長(zhǎng)度為奇數(shù)，不需要再計(jì)算下去了。
??????????????????????if(last[0].size()%2==1)?break;
??????????????????????last?=?tmp;??????????????????
????????????????????????
????????????????????????}
????????????????????return?res;
??????????????????}
??????????????
??????????????int?min_to_make_equal(vector<string>?&vs){
???????????????????memset(cnt,0,sizeof(cnt));
???????????????????int?i,j;
???????????????????for(i=0;i<vs[0].size();++i)
???????????????????????for(j=0;j<vs.size();++j)
???????????????????????????cnt[i][vs[j][i]-'a']++;
???????????????????vector<char>?equal;
???????????????????for(i=0;i<vs[0].size();++i){
???????????????????????int?max?=?0;
???????????????????????for(j=0;j<26;++j){
???????????????????????????if(cnt[i][j]>cnt[i][max])
???????????????????????????????max?=?j;
???????????????????????}
???????????????????????equal.push_back('a'+max);
???????????????????}
???????????????????int?res?=?0;
???????????????????for(i=0;i<vs.size();++i){
???????????????????????for(j=0;j<vs[i].size();++j){
????????????????????????if(vs[i][j]!=equal[j])
????????????????????????????res++;
???????????????????????}
???????????????????}
???????????????????return?res;
??????????????}
};
附原題：
“回文分?jǐn)?shù)”游戲并不簡(jiǎn)單。游戲的目標(biāo)是修改最多maxChanges個(gè)字符使得一個(gè)字符串word的回文分?jǐn)?shù)最高。只允許修改，不許增加或者刪除字
符。一個(gè)字符串的回文分?jǐn)?shù)定義如下：
如果字符串不是回文串，則分?jǐn)?shù)為0。
如果字符串是回文串，且長(zhǎng)度為奇數(shù)，則分?jǐn)?shù)為1。
如果字符串是回文串，且長(zhǎng)度為偶數(shù)，我們將它分為左右兩半。計(jì)算它的一半子串的回文分?jǐn)?shù)為K（兩個(gè)一半子串得分一定相同），則原字符串的回文分?jǐn)?shù)為K
+ 1。
給定一個(gè)字符串word和一個(gè)型整數(shù)maxChanges，返回最多修改maxChanges個(gè)字符后最大可能的回文分?jǐn)?shù)。
DEFINITION
Class:MaximumPalindromeScore
Method:maximize
Parameters:String, int
Returns:int
Method signature:int maximize(String word, int maxChanges)
NOTES
-回文串的定義是一個(gè)字符串從前向后讀和從后向前讀完全一樣。
CONSTRAINTS
-word包含1到50個(gè)字符（含1和50）。
-word 只包含小寫(xiě)字母 ('a'-'z')。
-maxChanges 取值范圍是0到50（含0和50）。
EXAMPLES
0)
"coder"
2
Returns: 1
我們可以把c改成r，把e改成o，得到"rodor"。這是一個(gè)奇數(shù)長(zhǎng)度的回文串，所以得分為1。
1)
"abcbxabcba"
1
Returns: 2
如果把x改成a，得到偶數(shù)長(zhǎng)度的回文串"abcbaabcba"。它的一半子串是奇數(shù)長(zhǎng)度的回文串"abcba"，所以子串分?jǐn)?shù)為K = 1，因而最后
得分是K + 1 = 2。
2)
"abcdefghijklmnop"
15
Returns: 5
可以把這個(gè)字符串修改成"aaaaaaaaaaaaaaaa"、"eeeeeeeeeeeeeeee"或其他14種串，回文得分均為5。
3)
"ssssssssssssssss"
15
Returns: 5
有時(shí)不做所有允許的改變可能更好。
4)
"vyyvvzzvvxxvvxxv"
4
Returns: 3
5)
"a"
0
Returns: 1