UVa 11552 – Fewest Flops [DP]

Link

传送门

Problem

A common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of times the character occurs followed by the character itself. For example, the string “aabbbaabaaaa” may be encoded as “2a3b2a1b4a”. (Note for this problem even a single character “b” is replaced by “1b”.)

Suppose we have a string S and a number k such that k divides the length of S. Let S1 be the substring of S from 1 to k, S2 be the substring of S from k + 1 to 2k, and so on. We wish to rearrange the characters of each block Si independently so that the concatenation of those permutations S ′ has as few chunks of the same character as possible. Output the fewest number of chunks.

For example, let S be “uuvuwwuv” and k be 4. Then S1 is “uuvu” and has three chunks, but may be rearranged to “uuuv” which has two chunks. Similarly, S2 may be rearranged to “vuww”. Then S ′ , or S1S2, is “uuuvvuww” which is 4 chunks, indeed the minimum number of chunks.

Mean

给出一个字符串, 并且给出一个k, 并且保证字符串可以分成若干段, 每段等长度k.每段里面的字符可以任意排列, 但是段与段之间顺序不变, 组合之后要使得字符串里面的块数最少, 相同的字符放在一起可以统计为一块, 一个字符也可以单独成块.

Analysis

首先统计出每段中含有的字符和总个数放在一个集合中,这样便于后面DP查询。然后定义状态dp[pos][ed]表示第pos段最后一个字符为ed时的答案,状态转移就枚举前一个段的ed分情况讨论。这样记忆化搜索即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024, inf = 0x3f3f3f3f;
vector<int> has[maxn];
int T, len, n, k, v[maxn][30], dp[maxn][30];
char s[maxn];

void init() {
    scanf("%d %s", &n, s);
    len = strlen(s);
    k = len / n;
    for(int i = 0; i < k; ++i) {
        has[i].clear();
        memset(v[i], false, sizeof(v[i]));
        for(int j = 0; j < n; ++j)
            v[i][s[i*n+j]-'a'] = true;
        for(int j = 0; j < 26; ++j)
            if(v[i][j])
                has[i].push_back(j);
    }
    memset(dp, -1, sizeof(dp));
}

int solve(int pos, int ed) {
    if(pos < 0) return 0;
    int & ans = dp[pos][ed];
    if(ans != -1) return ans;
    if(!v[pos][ed]) return ans = inf;
    if(pos == 0) return ans = has[0].size();
    ans = inf;
    for(auto & i : has[pos-1]) {
        int pre = solve(pos-1, i);
        if(!v[pos][i]) {
            ans = min(ans, pre + (int)has[pos].size());
        } else {
            if(i == ed && has[pos].size() == 1) ans = min(ans, pre);
            else if(i == ed) ans = min(ans, pre + (int)has[pos].size());
            else ans = min(ans, pre + (int)has[pos].size()-1);
        }
    }
    return ans;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        init();
        int ans = inf;
        for(auto i : has[k-1])
            ans = min(ans, solve(k-1, i));
        printf("%d\n", ans);
    }
    return 0;
}

欢迎留言