「USACO 2021 Jan Gold」Uddered but not Herd

若哼唱的字母歌中，后一个字母在字母表的中位置大于前一个字母的位置，则意味着又一遍的哼唱开始了。由此，我们得到本题的暴力解法：

暴力解法

设字母表中有 $n$ 个元素，哼唱的字符串长度为 len。那么，枚举的代价为 $O(n!)$，每次检查的代价为 $O(\text{len})$。总的时间复杂度为 $O(n! \times \text{len})$。不足以通过前 $3$ 个测试点。注意到每次检查，我们关心的是子串 $(str[i], str[i + 1])$ 满足 $str[i]$ 在字母表中出现的位置晚于等于 $str[i + 1]$，这种子串的数量。故我们可以提前预处理各种二元子串的数量。在枚举字母表的时候，统计不合法的子串数量即可。

参考代码

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

int main() {
  string str; cin >> str;
  map<char, int> mp;
  int num = 0;
  for (auto ch : str) {
    if (mp.find(ch) == mp.end()) mp[ch] = num++;
  }

  // 统计每个子串的数量
  vector<vector<int> >cnt(num, vector<int>(num, 0));
  for (int i = 1; i < str.size(); i++) cnt[mp[str[i - 1]]][mp[str[i]]]++;

  vector<int> p(num);
  iota(begin(p), end(p), 0);

  int ans = INT_MAX;
  do {
    int cur_ans = 0;
    for (int i = 0; i < num; i++) {
      for (int j = 0; j <= i; j++) {
        cur_ans += cnt[p[i]][p[j]];
      }
    }
    ans = min(ans, cur_ans);
  } while (next_permutation(begin(p), end(p)));
  cout << 1 + ans << ;
}

正解

暴力算法中，我们统计了输入字符串的所有的相邻字符组成的二元子串的数量，再枚举所有可能的字母表排列，计算最优的答案。

设 $S$ 为字母表的子集， $f[S]$ 表示前面的二元子串 $(x, y)$，满足所有字母均在 $S$ 中，且 $pos[x] \ge pos[y]$ 的最少子串数量。

我们假设某个字母 $c$ 是最后出现的字母，那么，现在所有的二元子串可能分为两类，含 $c$ 的子串和不含 $c$ 的子串。

对于不含 $c$ 的子串，依然是考虑最少的满足 $pos[x] \ge pos[y]$ 的数量，这正是 $f[S \setminus c]$ 的含义。

对于含 $c$ 的子串，我们只需考虑 $c$ 在前的子串数量即可。

$\displaystyle f[S] = \min_{c\in S} \{ f[S \setminus c] + \sum_{i \in S}cnt[c][i] \}$

参考代码

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

const int N = 20;
int cnt[N][N];
int f[1 << N];

int main() {
    string str; cin >> str;
    map<char, int> mp;
    int num = 0;
    for (auto ch : str) {
        if (mp.find(ch) == mp.end()) mp[ch] = num++;
    }

    for (int i = 1; i < str.size(); i++) cnt[mp[str[i - 1]]][mp[str[i]]]++;

    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int stat = 1;  stat < (1 << num); stat++) {
        for (int bit = 0; bit < num; bit++) {
            if ((stat >> bit) & 1) {
                int sum = 0;
                for (int j = 0; j < num; j++) {
                    if ((stat >> j) & 1) sum += cnt[bit][j];
                }
                f[stat] = min(f[stat], f[stat ^ (1 << bit)] + sum);
            }

        }
    }
    cout <<  + f[( << num) - ] << ;
}