Uddered But Not Hered (USACO Gold 2021 January)

首先这个题有个坑，把一个关键条件藏在了测试点性质里面：“测试点 $6-16$ 中，Farmer Nhoj 从未听到任何出现在 Mildred 名字中的字母。”，前面说字母一共有 $26$ 个，但这个条件是说FN听到的唯一字母数量只有 $26-7=19$ 。 $N=19$ 就指向bitmask DP这个方法（反过来如果 $N=26$ ，那bitmask DP就超时了）。所以不能漏掉这个条件。

具体怎么bitmask DP，我们观察题目：要求M唱的歌的最少次数，其实就是求输入字符串在一个特定的字母顺序下，“相邻逆序字母对”的最小次数最少。比如，如果字母顺序是ABCDE，那么ABCBA就需要至少三次，因为“CB”、“BA”都是“相邻逆序字母对”，再加基本的一次，一共唱三次。容易看到不同的字母顺序，导致唱的次数也不同。

虽然我们不知道具体的字母顺序，但我们可以求出输入串所有的相邻字母对的数量（ $19\cdot 19=361$ 个数），这时naive的方法就是枚举所有字母顺序，对于每个顺序，基于这些字母对数量统计，就可以快速算出有多少个逆序对了。但这个运算次数是 $19! \cdot 361$ ，过高。当然这时可以想到bitmask DP，它的经常用法就是把全排列复杂度降低到子集生成 $\mathcal{O}(2^n)$ ，就是我们面临的情况。

我们定义 $\text{dp}[b]$ 为bitmask $b$ 对应的字母下，相邻逆序对的最小数量，则结果就是 $\text{dp}[1<<m-1]$ （ $m$ 是字母数量）。

状态转移是： $\text{dp}[b] = \min_{i \in b} (dp[b \backslash i] + \sum_{j \in b \backslash i} C_{ji} )$

其中 $C_{ji}$ 是输入串中 $j$ 后面紧跟 $i$ 的次数。这个的意思是，我们枚举 $b$ 中字母序最前的字母 $i$ ，则最少的逆序对数量，就是除掉 $i$ 之外的字母中的逆序对数量，加上 $i$ 带来的贡献 $\sum_{j \in b \backslash i} C_{ji}$ （因为 $i$ 在字母表中最前，所以任何字母后面跟 $i$ 都是逆序对）。

复杂度是 $\mathcal{O}(2^n)$ ， $n=19$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m;
char s[100005];
int letters[128];
int l2n[128];       // letter to ids
int n2l[26];        // ids to letters (0-25)
int cnt[26][26];    // cnt[i][j], number of i followed by j pairs
int dp[1<<26];      // dp[bm], min # of "reversed pairs" with bitmask bm
int ans = INT32_MAX;
 
int main() {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; i++)
        letters[s[i]]++;
    for (char c = 'a'; c <= 'z'; c++)
        if (letters[c] > 0) l2n[c] = m, n2l[m++] = c-'a';
 
    for (int i = 0; i < n-1; i++)
        cnt[l2n[s[i]]][l2n[s[i+1]]]++;
    
    for (int bm = 1; bm < (1<<m); bm++) {
        dp[bm] = INT32_MAX;
        for (int i = 0; i < m; i++) {
            int bi = 1 << i;
            if (bm & bi) {
                // i is earliest in alpabet among bm
                int sum = 0;
                for (int j = 0; j < m; j++) {
                    int bj = 1 << j;
                    if (bm & bj)        // sum of all contributions (i followed by i also contributes)
                        sum += cnt[j][i];
                }
                dp[bm] = min(dp[bm], dp[bm ^ bi] + sum);
            }
        }
    }
    printf("%d", dp[(1<<m)-1] + 1);
    return 0;
}