[UVA][dp] 11552 - Fewest Flops
Problem F
FEWEST FLOPS
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.
Program Input
The input begins with a line containing t (1 ≤ t ≤ 100), the number of test cases. The following t lines contain an integer k and a string S made of no more than 1000 lowercase English alphabet letters. It is guaranteed that k will divide the length of S.
Program Output
For each test case, output a single line containing the minimum number of chunks after we rearrange S as described above.
INPUT
25 helloworld7 thefewestflopsOUTPUT
810
基本上看得出來是一個可以用滾動數組去完成的 dp，但是我居然一直錯。
dp[前i-1塊][結尾字元] 轉移 dp[前i塊][結尾字元]
找出 S[0...K-1] 中有多少不同的字元，再進行轉換，嘗試頭接到前一個結尾字元，
如果相同則可以減少一個塊。
※ 注意如果區間內只有一種字元，處理時不要犯錯。
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int mn(int x, int y) {
if(x == -1)
return y;
return x < y ? x : y;
}
int main() {
scanf("%*d");
char s[1005];
int K, i, j, k, l;
while(scanf("%d %s", &K, s) == 2) {
int len = strlen(s);
int dp[2][26] = {}, flag = 1, mnn;
for(i = 0; i < 26; i++)
dp[0][i] = -1;
for(i = 0; i < len; i += K) {
sort(s+i, s+i+K);
s[0] = s[i]-'a';
for(j = 1, k = 0; j < K; j++)
if(s[i+j]-'a' != s[k])
s[++k] = s[i+j]-'a';
mnn = 0xffff;
/*for(j = 0; j <= k; j++)
printf("%c", s[j]+'a');
puts("");*/
for(j = 0; j < 26; j++) {
dp[flag][j] = -1;
if(dp[!flag][j] != -1)
mnn = min(mnn, dp[!flag][j]);
}
if(mnn == 0xffff) mnn = 0;
if(k == 0) {
dp[flag][s[0]] = mnn+1;
if(dp[!flag][s[0]] != -1)
dp[flag][s[0]] = mn(dp[flag][s[0]], dp[!flag][s[0]]);
flag = !flag;
continue;
}
for(j = 0; j <= k; j++) {
if(dp[!flag][s[j]] != -1) {
for(l = 0; l <= k; l++) {
if(l == j) {}
else
dp[flag][s[l]] = mn(dp[flag][s[l]], dp[!flag][s[j]]+k);
}
}
}
for(j = 0; j <= k; j++)
dp[flag][s[j]] = mn(dp[flag][s[j]], mnn+k+1);
/*for(j = 0; j < 26; j++)
printf("%d ", dp[flag][j]);
puts("");*/
flag = !flag;
}
mnn = 0xffff;
for(i = 0; i < 26; i++)
if(dp[!flag][i] != -1)
mnn = min(mnn, dp[!flag][i]);
printf("%d\n", mnn);
}
return 0;
}
/*
2
5 helloworldlllll
/hello/ordwl/lllll => 8
*/