UVA 11552 Fewest Flops

題意： 輸入一個正整數k和字元串s，串的長度保證是k的倍數，把s的字元按照從左到右的順序每k個分為一組，每組之間可以任意重排，但組之間的先後順序保持不變。你的任務是讓重排後的字元串包含盡量少的“塊”，其中每個塊為連續的相同字母。

解法： 設dp[i][j]為以字母i結尾塊數為j的串的最少塊數，有如下狀态轉移：

若塊j的元素種類大于1，塊j中存在元素x且塊j中的元素種類為m，則dp[i][j] = min(dp[i][j], dp[x][j-1]) + m - 1，i為塊j中非x的字母，若塊j-1不存在字母x，則去掉後面的-1。

若塊j的元素種類等于1，假定隻存在字元x，則dp[x][j] = min(dp[i][j-1]) + 1,再判斷塊j-1是否存在x結尾的串，存在則dp[x][j] = min(dp[x][j], dp[x][j-1])。

當給的k等于1時注意判一些細節。

/* **********************************************
Author      : Nero
Created Time: 2013-8-25 16:21:12
Problem id  : UVA 11552
Problem Name: Fewest Flops
*********************************************** */

/*

需要注意給定k等于1的情況

*/

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(int)(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))

const int INF = ~0u>>2;
int dp[26][1010];
char s[1010];
int k,len;
int mark[26][1010];

int main() {
    int cas;
    scanf("%d", &cas);
    while(cas--) {
        scanf("%d%s", &k, s+1);
        len = strlen(s+1);
        REP(i,0,26) REP(j,1,len+1) dp[i][j] = INF;
        clr(mark,0);
        for(int i = 1; i+k-1 <= len; i += k) {
            int b = i/k + (k != 1), cnt = 0;
            for(int j = i; j < i+k; j ++) {
                mark[s[j]-'a'][b] ++;
                if(mark[s[j]-'a'][b] == 1) cnt ++;
            }
            if(cnt == 1) {
                int c;
                for(c = 0; c < 26; c ++) if(mark[c][b]) break;
                if(b == 1) {
                    dp[c][b] = 1;
                    continue;
                }
                if(mark[c][b-1]) dp[c][b] = dp[c][b-1];
                for(int j = 0; j < 26; j ++) if(mark[j][b-1]) {
                    dp[c][b] = min(dp[c][b], dp[j][b-1] + 1);
                }
            }
            else {
                for(int c = 0; c < 26; c ++) if(mark[c][b]) {
                    if(b == 1) {
                        dp[c][b] = cnt;
                        continue;
                    }
                    for(int j = 0; j < 26; j ++) if(mark[j][b-1]) {
                        if(mark[j][b] && j != c) dp[c][b] = min(dp[c][b], dp[j][b-1] + cnt - 1);
                        else dp[c][b] = min(dp[c][b], dp[j][b-1] + cnt);
                    }
                }
            }
        }
        int minx = INF;
        REP(i,0,26) minx = min(minx, dp[i][len/k]);
        printf("%d\n", minx);
    }
    return 0;
}