首页 > 代码库 > uva 11552 dp
uva 11552 dp
UVA 11552 - Fewest Flops
一个字符串,字符串每 k 个当作一组,组中的字符顺序能够重组。问经过重组后改字符串能够编程最少由多少块字符组成。连续的一段字符被称为块。
dp[i][j] 表式第i组以字符j结尾的最少块数。
那么我们考虑加入一组后能够降低块数的情况。
1):上一组的结尾在这一组里找得到相同的字符,而且该字符不作为当前块的结尾。
假设要作为结尾的话要把该字符所在的块拆开。所以然并卵。
2):当前组仅仅有一种字符,而且和上一组的结尾相同。
这两种情况都能够使块数减一
dp[i][s] = min(dp[i-1][t] + cnt[i] - flag);flag表示是否满足上述两种情况。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 999999999;
char s[1005];
int c[1005][26];
int dp[1005][26];
int _cnt[1005];
int k, len;
int main() { // freopen("out.txt", "w", stdout);
int Tcase;
scanf ("%d", &Tcase);
for (; Tcase>0; --Tcase) {
scanf ("%d%s", &k, s);
len = strlen(s);
int _c=-1;
memset(c, 0, sizeof(c));
memset(_cnt, 0, sizeof(_cnt));
while (_c<len/k) {
for (int j=0; j<k; j++) {
if (c[_c][s[_c*k+j]-‘a‘] == 0) _cnt[_c]++;
c[_c][s[_c*k+j]-‘a‘]++;
}
_c++;
}
for (int i=0; i<=_c; i++) {
for(int j=0; j<26; j++) {
dp[i][j] = INF;
}
}
for (int i=0; i<26; i++) {
if (c[0][i] != 0) dp[0][i] = _cnt[0];
else dp[0][i] = INF;
}
for (int i=1; i<_c; i++) {
for (int s=0; s<26; s++) {
for (int t=0; t<26; t++) {
if (c[i][s] == 0) continue;
if (c[i-1][t] == 0) continue;
if (c[i][t] != 0 && (_cnt[i] == 1 || s != t)) {
dp[i][s] = min(dp[i][s], dp[i-1][t] + _cnt[i] - 1);// cout << s << " " << t << endl;
} else {
dp[i][s] = min(dp[i][s], dp[i-1][t] + _cnt[i]);
}
}
}
}
int ans = INF;
for (int i=0; i<26; i++) {
ans = min(ans, dp[_c-1][i]);
}
printf ("%d\n", ans);
}
return 0;
}
uva 11552 dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。