题意: 给一个长度为n的串n<1000然后将这个串平均分成k分,分别为 s1 s2 s3...sk,这k份中可以任意的交换字母位置 比如uuvuwwuv 切成两份 这样 uuvu 和wwuv 这样然后 重新整理一下就得到了 uuuv 和vuww 这样合并uv和vuw 在将两个合并 得到 uvuw 为4 个能在消的字符，问最后最小的结果是多少。刚开始考虑 交换他们的不同匹配，因为只要考虑两端就行了，贪心的进行交换结果wa了， 考虑dp[i][c]表示在第i部分的末尾放c的最小值，特判只有1种的情况 然后其他的 不能自己当头又当尾就行了 从前一个状态转移而来 如果有相同的就 +len[i]-1 否则就 +len[i]
dp[i][c]=min(dp[i-1][j]+v)j!=c 特判 1 ，v= i中有没有j ?len[i]-1:len[i];
#include <iostream> #include <cstdio> #include <string.h> #include <vector> using namespace std; const int maxn = 1005; int dp[maxn][30]; int ch[maxn][30]; int len[maxn]; vector<int> common[maxn]; char str[maxn]; int k,num; void inti(int n ){ for(int i=0; i<=n; ++i) for(int j=0; j<26; ++j) dp[i][j]=maxn; } int main() { int cas; scanf("%d",&cas); for(int cc=1; cc<=cas; ++cc){ scanf("%d%s",&k,str); int L = strlen(str); num=1; for(int i=0; i<L; i+=k){ len[num]=0; memset(ch[num],0,sizeof(ch[num])); for(int j=i; j<i+k; ++j) ch[num][str[j]-'a']=1; common[num].clear(); for(int j=0; j<26; ++j) if(ch[num][j]==1){ common[num].push_back(j); len[num]++; } num++; } inti(num); for(int i=0; i<common[1].size(); ++i) dp[1][common[1][i]]=len[1]; for(int i=2; i<num; ++i){ int sz=len[i]; if(sz==1){ int t=common[i][0]; for(int j=0; j<26; ++j) if(t==j) dp[i][t]=min(dp[i][t],dp[i-1][j]+sz-1); else dp[i][t]=min(dp[i][t],dp[i-1][j]+sz); }else { for(int j=0; j<26; ++j) for(int d=0; d<sz; ++d){ int t=common[i][d]; if(ch[i][j]==1&&t!=j) dp[i][t]=min(dp[i][t],dp[i-1][j]+sz-1); if(ch[i][j]==0) dp[i][t]=min(dp[i][t],dp[i-1][j]+sz); } } } int ans=maxn; for(int i=0; i<26; ++i) ans=min(ans,dp[num-1][i]); printf("%d ",ans); } return 0; }