UVA 11552: Fewest Flops —— 动态规划

题目链接 ( UVA 主站好像上不去…这个是 VJudge 上这道题的链接)

题目大意:

给你一个字符串 $s$ 。我们将 $s$ 每 $k$ 个分为一组 ( 保证 $s$ 的长度是 $k$ 的整数倍 ),在每一个分组内可任意调换字符的顺序。我们把一段只有相同字符的子串称作一个块。求在经过变换之后,字符串 $s$ 最少可以拥有多少个块。

输入格式:

第一行一个整数 $T$ ,代表测试数据数量。

对于每一组测试数据,第一个整数 $k$ ,含义如题面所述。然后一个字符串,保证字符串的长度是 $k$ 的整数倍。

输出格式:

对于每组测试数据,输出最少的块数。

测试样例:

Input
2
5 helloworld
7 thefewestflops
Output
8
10

分析:

这道题乍一看,思路其实非常清晰。

首先在一个分组里,数字的种类数就是这个分组内最少的块数,因为分组内是可以任意变换顺序的。

在考虑合并两个分组时,如果前一个分组的结尾与后一个分组的开头的字母相同,合并的块数是两个分组的块数相加后减 $1$ ,如果不相同,就直接相加。

思路就这么简单。现在我们考虑如何定义 DP 的状态。

经过一番思考与尝试,定义一个二维的状态 $dp_{i,j}$ 存储前 $i$ 个分组的最小块数。 $j$ 代表第 $i$ 个块以字母 $j+48$ 结尾。

在进行状态转移之前,我们要预处理出一些东西方便使用:

  • $flag_{i,j}$: 代表第 $i$ 个分组里有没有 $j + 48$ 这个字母。布尔型。
  • $cnt_i$: 代表第 $i$ 个分组的字母种类数 ( 也就是最小分块数 ) 。

然后我们再开始动态规划:

第一层循环顺序 $i$ 枚举分组,第二层循环 $j$ 枚举 26 个字母作为上一个分组的结尾,第三层循环 $k$ 依然枚举 26 个字母作为当前分组的结尾。

如果枚举到的上一个分组结尾字母在当前分组中出现了,那么在上一个分组以该字母结尾并且当前分组不以该字母结尾的情况下,更新答案时在加上 $cnt_i$ 后要减 $1$ :因为如果当前分组不以该字母结尾,那就必须得让它开头,这样才能保证最优。当然,如果上一个分组的结尾与当前分组的结尾是一样的,那么就不能减 $1$ 了。但是,这里有一个特殊情况:如果当前分组只有一种字母,也就是 $cnt_i = 1$ ,那么该分组既以它开头,又以它结尾,刚刚的状态转移就会冲突,所以应该特判:如果 $cnt_i = 1$ ,块的个数是不会增加的 ( 不要忘了我们现在所处的情况是「枚举到的上一个分组的结尾字母在当前分组有出现过」) 。

以上是第一种大情况。这个转移长得像这样:

if (dp[i - 1][j] < INF) {
  if (flag[i][j]) {
    if (cnt[i] == 1) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        continue;
    }
    for (int k = 0; k < 26; ++k) {
      if (flag[i][k] && k != j) {
        dp[i][k] = min(dp[i][k], dp[i - 1][j] + cnt[i] - 1);
      }
    }
    dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt[i]);
  }


如果当前枚举到的上一个分组的结尾字母并没有在当前分组出现,那么对于当前分组出现的所有字母 $k$ ,更新答案时都直接加上 $cnt_i$ 就好,不存在减 $1$ 的情况。

以上是第二种大情况。转移像这样:

for (int k = 0; k < 26; ++k) {
  if (flag[i][k]) dp[i][k] = min(dp[i][k], dp[i - 1][j] + cnt[i]);
}


完成动态规划后,最后答案是 $min(dp_{i,j})+1\ (0 \leq j \leq 26)$ (为什么要加 $1$ ?好好想想吧)。

代码:

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

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _t = getchar(), _flag = 1;
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 1000 + 100, INF = 0x3f3f3f3f;
int nk, cnt[MAX_N];
char s[MAX_N];
int flag[MAX_N][30];
int dp[MAX_N][30];

void DP() {
  for (int i = 0; i < 26; ++i)
    dp[0][i] = 0;
  int len = strlen(s);
  for (int i = 1; i <= len / nk; ++i) {
    for (int j = 0; j < 26; ++j) {
      if (dp[i - 1][j] < INF) {
        if (flag[i][j]) {
          if (cnt[i] == 1) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            continue;
          }
          for (int k = 0; k < 26; ++k) {
            if (flag[i][k] && k != j) {
              dp[i][k] = min(dp[i][k], dp[i - 1][j] + cnt[i] - 1);
            }
          }
          dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt[i]);
        }
        else {
          for (int k = 0; k < 26; ++k) {
            if (flag[i][k]) dp[i][k] = min(dp[i][k], dp[i - 1][j] + cnt[i]);
          }
        }
      }
    }
  }
}

int main() {
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  int T;
  read(T);
  while (T--) {
    read(nk);
    scanf("%s", s);
    memset(dp, INF, sizeof(dp));
    memset(flag, 0, sizeof(flag));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < strlen(s); ++i) {
      flag[i / nk + 1][s[i] - 'a'] = 1;
    }
    for (int i = 1; i <= strlen(s) / nk; ++i) {
      for (int j = 0; j < 26; ++j)
        if (flag[i][j]) ++cnt[i];
    }
    DP();
    int fn = strlen(s) / nk, ans = INF;
    for (int i = 0; i < 26; ++i)
      ans = min(dp[fn][i], ans);
    printf("%d\n", ans + 1);
  }
  return 0;
}