Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
Peter has a string s=s1s2...sn of even length. He wants to find a lexicographically smallest square string t=t1t2...tn that the hamming distance between s and t is exact m. In addition, both s and t should consist only of lowercase English letters.
The first contains two integers n and m (1≤n≤1000,0≤m≤n,n is even) -- the length of the string and the hamming distance. The second line contains the string s.
题意：给你一个长度为n的s串，一个数m，现在让你构造一个长度也为n的t串，使这个串是由两个相同的串拼起来的，并且和s串对应的位不同的数量为m。
而且使t的字典序尽量小。
一开始会想到贪心，但是显然单纯的贪心无法得到正确结果。于是要利用到dp
dp[i][count]表示取到i位有count个位置不一样是否成立。dp[i][count]+=dp[i+1][count-gg](gg表示要变的位置数）
这题要分几种情况
（1）s[i]==s[i+n/2]，这个时候要么不变位置要么就变2次。
（2）s[i]!=s[i+n/2]，这是要么变2次要么变1次。
由于要求字典序要最小，所以尽量要从首位开始变。于是递推要从n/2开始，这样才能保证前面的操作能使后续操纵成立。
#include <iostream>
#include <cstring>
using namespace std;
char s[1010];
int dp[1010][1010];
int main()
{
int t;
cin >> t;
while(t--) {
int n , m;
cin >> n >> m;
cin >> (s + 1);
int count = m;
memset(dp , 0 , sizeof(dp));
dp[n / 2 + 1][0] = 1;
for(int i = n / 2 ; i >= 1 ; i--) {
if(s[i] == s[i + n / 2]) {
for(int j = 0 ; j <= m ; j++) {
dp[i][j] += dp[i + 1][j];
}
for(int j = 2 ; j <= m ; j++) {
dp[i][j] += dp[i + 1][j - 2];
}
}
else {
for(int j = 1 ; j <= m ; j++) {
dp[i][j] += dp[i + 1][j - 1];
}
for(int j = 2 ; j <= m ; j++) {
dp[i][j] += dp[i + 1][j - 2];
}
}
}
if(!dp[1][m]) {
cout << "Impossible" << endl;
continue;
}
for(int i = 1 ; i <= n / 2 ; i++) {
for(int j = 0 ; j < 26 ; j++) {
int temp = (s[i] != j + 'a') + (s[i + n / 2] != j + 'a');
if(dp[i + 1][m - temp]) {
s[i] = s[i + n / 2] = j + 'a';
m -= temp;
break;
}
}
}
cout << s + 1 << endl;
}
return 0;
}