Uva(11552)(Fewest Flops)

链接：https://vjudge.net/problem/UVA-11552
思路：就动态规划加枚举就完事了，有以下贪心在里面：当上一个结尾为k时，则下一个的结尾肯定不为j，且一个大块中所有相同的要连在一起，注意动态规划时第一块要拿出来单独处理，因为他左边没有块所以跟其他的处理方式不太一样，复杂度的话O(n)，后面枚举的时候枚举前一块的结尾和后一块的结尾，如果二者相等则跳过，不等则查询一下后一块中是否有前一块结尾，有的话就可以把加的长度-1，否则不行，然后遍历最后一块的结尾即可得到最大值
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

int tt,n;
string a;
int dp[1001][26];
int c[1001][26];//查询某一个大块中某个小连块有多少个
int t[1001];//查询某一个大块中有多少种小连块

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>tt;
    while(tt--){
        memset(c,0,sizeof(c));
        memset(t,0,sizeof(t));
        cin>>n>>a;
            for(int i=1;i<=a.size()/n;i++){//全部赋值为无穷大，代表该状态不存在
            for(int j=0;j<26;j++){
                dp[i][j] = 1e9;
            }
        }
//读入每一大块的小块信息
    for(int i=0;i<a.size()/n;i++){
        for(int j=0;j<n;j++){
        if(c[i][a[i*n+j]-'a']++==0)t[i]++;
        }
    }
//第一块单独处理
    for(int i=0;i<26;i++){
                if(c[0][i]){
                    dp[0][i] = t[0];
                }
                else dp[0][i] = 1e9;
            }

    for(int i=0;i<a.size()/n-1;i++){
        for(int j=0;j<26;j++){
            if(c[i+1][j]==0)continue;
            for(int k=0;k<26;k++){
                if(j==k&&t[i+1]>1)continue;//如果j=k且小连块种类大于1，则绝对不是最优解，等于1他既是头又是尾
                else if(c[i][k]&&c[i+1][k])dp[i+1][j] = min(dp[i+1][j],dp[i][k] + t[i+1] - 1);
                else dp[i+1][j] = min(dp[i+1][j],dp[i][k]+t[i+1]);
            }
        }
    }
    int ans = 1e9;
    for(int i=0;i<26;i++){
        ans = min(ans,dp[a.size()/n-1][i]);
    }
    cout<<ans<<endl;
    }
    return 0;
}