一个区间一个区间的考虑，当前区间的决策只和上一次的末尾有关，考虑转移的时候先统计当前区间出现过的字母以及种数ct

枚举上一个区间的末尾标号j，规定小于INF为合法状态，确定j之后看j有没有在当前的区间出现，如果出现则贪心选块数+ct-1，

枚举当前的结尾。为了方便处理，增加一个0区间，初始为0，这样所有的块数会减1，转移完以后在加上1。

#include
     
      using namespace std;const int LEN = 1e3+3;int dp[LEN][26];char s[LEN];const int INF = 0x3f3f3f3f;//#define LOCALint 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]