UVA 11552 Fewest Flops（序列划分模型；状态设计）

冷不防 2021-12-12 16:07 142阅读 0赞

## 题意：给一个正整数k和字符串s，s的长度是k的倍数，把s每k个字符分成一组，没组之间的字符可以任意重排，但组与组之间的顺序保持不变。任务是让重排后的新字符串s'的块最少，连续相同的字符组成一个块,比如abbbaa有三个块a、bbb、aa。 ##

## 分析：主要在于块与块交接处的影响，即末尾和开头部分，组内直接贪心把相同的相邻放就行，dp\[i\]\[j\]表示前i组，以j结尾的最少块数，dp\[i\]\[j\] 转移时要转移到全部的dp\[i-1\]\[k\] 分成k等于j和k不等于j分别考虑。当第i-1个字串中出现了与第i个字串中相同的字母并且第i个字串只有一个chunks或者第i个子串的最后一个字母跟第i-1个字串的最后一个字母不相等的话，那么dp\[i\]\[j\] = min(dp\[i\]\[j\],dp\[i - 1\]\[k\] + chunks - 1); 否则dp\[i\]\[j\] = min(dp\[i\]\[j\],dp\[i - 1\]\[k\] + chunks)。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    int T,t,k,vis[30],dp[1005][1005];
    char s[1005];
    
    int main() {
        scanf("%d",&T);
        while(T--) {
            scanf("%d%s",&k,s);
            int len=strlen(s),bk=len/k;
            memset(dp,inf,sizeof(dp));
            for(int i=0;i<bk;i++) {
                memset(vis,0,sizeof(vis));
                for(int j=0;j<k;j++) {
                    int t=i*k+j;
                    vis[s[t]-'a']++;
                }
                int cnt=0;
                for(int j=0;j<30;j++)
                    if(vis[j]) cnt++;
                if(i==0) {
                    for(int j=0;j<k;j++)
                        dp[i][j]=cnt;
                }else {
                    for(int j=0;j<k;j++) {
                        int t=i*k+j;
                        for(int p=0;p<k;p++) {
                            int pre=(i-1)*k+p;
                            if( vis[s[pre]-'a'] && (cnt==1 || s[pre]!=s[t] ))
                                dp[i][j]=min(dp[i][j],dp[i-1][p]+cnt-1);
                            else dp[i][j]=min(dp[i][j],dp[i-1][p]+cnt);
                        }
                    }
                }
            }
            int ans=inf;
            for(int i=0;i<k;i++) ans=min(ans,dp[bk-1][i]);
            printf("%d\n",ans);
        }
        return 0;
    }