飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=28550

题意：给你一个字符串，假设长度为len，分割成len/k个字符串，假设一共有n个，每个被分割的部分可以随便重组，然后将n个字符串按1~n顺序排列，求最少的块，块定义为连接的是相同的字母。

分析：DP 复杂度n*26*26

起先我们可以将n个字串进行预处理，记录每个字母在当前串是否存在，不需要记录多少个（因为我们贪心的想法，肯定会把同一个串里同一个字母合在一起，这样才最优），然后我们记录长度，因为长度为1的要特殊处理,假设存在数组为ai，长度数组为bi，然后我们dp，假设当前处理的是i，如果bi[i]不等于1，那么我们枚举i里面的字母，如果当前字母是j，如果i-1也存在j，那么我们可以把i-1里面不是用j放第一的那种方案拿过来然后加上当前的bi[i]-1和我们当前的方案比一下，取最小的,因为合并，所以少了1个，假设我们定义数组islast记录把字母放在最后的最优解，计算好后，我们就知道把j放在当前的第一最优解是多少了，然后枚举其他不是j的，更新把他们放在最后的最优解。。。结束后，我们要更新最优解，因为最优解加上bi[i+1]就是i+1不管怎么排的下限、、、

这里我只处理了bi!=1，如果等于1,就好办了，直接把当前的最优和i-1存在j的比一下就好了，相当于直接把j扔到i-1里去了具体DP思想看代码。。。啪啪啪，就可以AC了

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define INF 1e9
using namespace std;
const int maxn=1234;
int k,T;
char ch[maxn];
bool ai[maxn][27];
int islast[maxn][27];
int bi[maxn];
void init()
{
    scanf("%d%s",&k,ch+1);
}
void play()
{
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    int len=strlen(ch+1);
    int n=len/k;
    for(int i=0; i<=n; i++)
        for(int j=1; j<=26; j++)islast[i][j]=INF;
    for(int i=1; i<=n; i++)
    {
        int st=(i-1)*k+1;
        int en=i*k;
        for(int j=st; j<=en; j++)
        {
            int p=ch[j]-'a'+1;
            if(!ai[i][p])bi[i]++;
            ai[i][p]=1;
        }
    }
    int before=0;
    for(int i=1; i<=n; i++)
    {
        before+=bi[i];
        int now=before;
        if(bi[i]==1)
        {
            for(int j=1; j<=26; j++)
            {
                if(ai[i][j])
                {
                    islast[i][j]=min(before,islast[i-1][j]);
                    now=islast[i][j];
                    break;
                }
            }

        }
        else
        {
            for(int j=1; j<=26; j++)
            {
                if(!ai[i][j])continue;
                int tm=min(islast[i-1][j]-1+bi[i],before);
                for(int k=1; k<=26; k++)
                {
                    if(ai[i][k]&&k!=j)
                    {
                        islast[i][k]=min(islast[i][k],tm);
                    }
                }
                now=min(tm,now);
            }
        }
        before=now;
    }
    int MIN=INF;
    for(int i=1; i<=26; i++)
    {
        MIN=min(islast[n][i],MIN);
    }
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//   cout << "Hello world!" << endl;
    return 0;
}