一个区间一个区间的考虑，当前区间的决策只和上一次的末尾有关，考虑转移的时候先统计当前区间出现过的字母以及种数ct
枚举上一个区间的末尾标号j，规定小于INF为合法状态，确定j之后看j有没有在当前的区间出现，如果出现则贪心选块数+ct-1，
枚举当前的结尾。为了方便处理，增加一个0区间，初始为0，这样所有的块数会减1，转移完以后在加上1。
#include<bits/stdc++.h> using namespace std; const int LEN = 1e3+3; int dp[LEN][26]; char s[LEN]; const int INF = 0x3f3f3f3f; //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int T; cin>>T; //for(int i = 1; i < 26; i++) dp[0][i] = 1; //memset(dp[0],0x3f,sizeof(dp[0])); while(T--){ int k; scanf("%d%s",&k,s); int len = strlen(s), mi = len/k; for(int i = 1; i <= mi; i++){ bool exs[26] = {}; for(int j = (i-1)*k; j < i*k; j++){ exs[s[j]-‘a‘] = true; } int ct = 0; for(int j = 0; j < 26; j++) ct += exs[j]; memset(dp[i],0x3f,sizeof(dp[i])); for(int j = 0; j < 26; j++){ if(dp[i-1][j]<INF){ if(exs[j]){ if(ct == 1) { dp[i][j] = min(dp[i][j],dp[i-1][j]); continue; } for(int k = 0; k < 26; k++){ if(exs[k] && k != j){ dp[i][k] = min(dp[i][k],ct-1+dp[i-1][j]); } } dp[i][j] = min(dp[i][j],ct+dp[i-1][j]); }else { for(int k = 0; k < 26; k++){ if(exs[k]){ dp[i][k] = min(dp[i][k],ct+dp[i-1][j]); } } } } } } int ans = INF; for(int j = 0; j < 26; j++) ans = min(dp[mi][j],ans); printf("%d\n",ans+1); } return 0; }
原文：http://www.cnblogs.com/jerryRey/p/4850537.html