题意：给一个正整数k和字符串s，s的长度是k的倍数，把s每k个字符分成一组，没组之间的字符可以任意重排，但组与组之间的顺序保持不变。
任务是让重排后的新字符串s'的块最少，连续相同的字符组成一个块,比如abbbaa有三个块a、bbb、aa。
首先每一组子串中相同的字符肯定要放在一起，然后问题就变成怎么排列这些子串中的块。
用dp[i][fa]表示前i组且第i+1组的最左边的字符是fa+'a'的状态能得到的最少的块数
那么状态的转移就是两层循环枚举这个第i组最左边和最右边应该放上什么字符，如果最右边和前一组的最左边一样，那么总块数就是加上（X-1)否则加上X，X表示这一组中字符的种类，也就是这一组中块的数量。
注意当一组中只有一种字符的特殊情况。
vector<int> g[1010]; int n; int dp[1010][27]; int f(int k,int fa) { if(dp[k][fa]>=0)return dp[k][fa]; if(k==0)return 0; vector<int> &ans=g[k]; int minn=INF; for(int i=0;i<ans.size();i++) { int num=(ans[i]!=fa?ans.size():(ans.size()-1)); for(int j=0;j<ans.size();j++) { minn=min(minn,f(k-1,ans[j])+num+(j==i&&ans.size()>1?1:0)); } } return dp[k][fa]=minn; } int main() { int t; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { int k; char s[1100]; scanf("%d%s",&k,s); n=0; for(int i=0;s[i]!=' ';i+=k) { char str[1100]; for(int j=i;j<i+k;j++) str[j-i]=s[j]; str[k]=' '; sort(str,str+k); g[++n].clear(); for(int j=0;j<k;j++) if(str[j]!=str[j+1])g[n].push_back(str[j]-'a'); } memset(dp,-1,sizeof(dp)); int num=f(n,26); printf("%d ",num); } return 0; }