这个题目刚看到还真不好下手，把一个是 k的倍数的长度的字符串分成len/k块，每块是k个字母，每个块可以重新组合，最后使得整个序列的相同字母尽量在一起，也就是说，最后会把序列从前往后扫，相连的相同字母算一个块，最后使得所有块最少。
这个其实是个从前往后扫的问题，只要枚举最后一位是哪个，比如i-1块的最后一位是w,且w在第i块中确实有，则 f[i][j]=min(本身，f[i-1][w]+chunks[i]-1), chunks[i]表示该块有本身有多少个小块。
#include <iostream> #include <cstdio> #include <cstring> #define INF 1<<30 char ch[1010]; int rec[1010]; int f[1005][1005]; int vis[1005][200]; int k; int min(int a,int b) { if (a<b) return a; return b; } int main() { int t; scanf("%d",&t); while (t--) { scanf("%d %s",&k,ch); int len=strlen(ch); memset(rec,0,sizeof rec); memset(vis,0,sizeof vis); memset(f,0,sizeof f); for (int i=0;i<len/k;i++) { for (int j=0;j<k;j++) { f[i][j]=INF; } for (int j=i*k;j<(i+1)*k;j++) { vis[i][ch[j]]++; } for (int j='a';j<='z';j++) { if (vis[i][j]) rec[i]++; //计算chunks } } for (int i=0;i<k;i++) { f[0][i]=rec[0]; //预处理第0位 } for (int i=1;i<len/k;i++) { for (int j=0;j<k;j++) { for (int w=0;w<k;w++) { int rear=i*k+j; int pre=(i-1)*k+w; if (vis[i][ch[pre]] &&(rec[i]==1 || ch[pre]!=ch[rear])) //如果第i位有第i-1位的该字母，则，除非第i位的chuanks=1，否则就必须第i位的最后一位不为该字母(该字母要放在序列头，则满足该条件) { f[i][j]=min(f[i][j],f[i-1][w]+rec[i]-1); } else { f[i][j]=min(f[i][j],f[i-1][w]+rec[i]); } } } } int ans=INF; for (int i=0;i<k;i++) { ans=min(ans,f[len/k-1][i]); } printf("%d ",ans); } return 0; }