UVa 11552 最小的块数（序列划分模型：状态设计）

题意：
输入一个正整数k和字符串S，字符串的长度保证为k的倍数。把S的字符按照从左到右的顺序每k个分成一组，每组之间可以任意重排，但组与组之间的先后顺序应保持不变。你的任务是让重排后的字符串包含尽量少的“块”，其中每个块为连续的相同字母。

思路：

令d【i】【j】表示第i组中第j位为末尾时的最小块数。

对于第【i】组，我们首先计算出它的块数，即不同字母的个数。

接下来枚举【i】组中第j个字母作为末尾时的情况，根据第【i-1】组中的字母，如果【i-1】中有和第【i】组相同的字母，此时如果【i】组只有一个块或者相同的字母不在【i】组末尾时：

d[i][j]=min(d[i][j],d[i-][p]+chunk-);

这样就可以前后相同的相连，减少一个块。

没有相同的字母的话那就只能是两者块相加了：

d[i][j]=min(d[i][j],d[i-][p]+chunk);

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long LL;

 typedef pair<int,int> pll;

 const int INF=0x3f3f3f3f;

 const int maxn=+;

 int k;

 char str[maxn];

 int d[maxn][maxn];

 int vis[];

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&k);

         scanf("%s",&str);

         int len=strlen(str);

         memset(d,INF,sizeof(d));

         for(int i=;i<len/k;i++)

         {

             memset(vis,,sizeof(vis));

             for(int j=;j<k;j++)

             {

                 int t=i*k+j;

                 vis[str[t]]=;

             }

             int chunk=;

             for(int c='a';c<='z';c++)

                 if(vis[c])   chunk++;

             if(i==)   //第一组的话直接赋值

                 for(int j=;j<k;j++)

                 d[i][j]=chunk;

             else

             {

                 for(int j=;j<k;j++)

                 {

                     int t=i*k+j;

                     for(int p=;p<k;p++)  //考虑第i-1组的各个字母

                     {

                         int pre=(i-)*k+p;

                         if(vis[str[pre]] && (chunk==||str[pre]!=str[t]))

                             d[i][j]=min(d[i][j],d[i-][p]+chunk-);

                         else d[i][j]=min(d[i][j],d[i-][p]+chunk);

                     }

                 }

             }

         }

         int ans=INF;

         for(int i=;i<k;i++)

             ans=min(ans,d[len/k-][i]);

         printf("%d\n",ans);

     }

     return ;

 }