E. Keyboard Purchase

题意

给定一个长度为 $n$ 的字符串 $s$ 仅由前 $m$ 个小写字母组成

现在要求求出包含前 $m$ 个小写字母的键盘，使得在键盘上敲出 $s$ 要移动的距离最短

移动总距离为：${\sum }_{i=2}^n|po{s}_{s_{i-1}}-po{s}_{s_i}|$

$po{s}_{s_i}$ 是 $s_i$ 在键盘上的位置

思路

由于 $m$ 很小，我们考虑在键盘上跑状压 $DP$，如果当前已经排好了集合 $S$ 中的那些位，枚举当前的字母的话，假设当前枚举的不在 $S$ 中的字母为 $i$，那么我们就需要找到 $s$ 中和字母 $i$ 相邻的那些字母 $j$，因为它们相邻，所以要 $j\to i$ 或 $i\to j$ 移动，这个移动是在键盘上移动的。我们不妨以 $cnt[i][j]$ 来表示原 $s$ 中相邻的 $i-j$ 配对数量

那么这一位放 $i$ 的贡献为：

• ${\sum }_{j\in S}cnt[j][i]\times (po{s}_i-po{s}_j)$
• ${\sum }_{j\notin S}cnt[j][i]\times (po{s}_j-po{s}_i)$

对于 $j$ 是否已经在 $S$ 中分开考虑，已经在 $S$ 中的 $j$，后放置的 $i$ 的 $po{s}_i$ 一定大于 $po{s}_j$，反之也很容易得出相应结论。

那么我们把贡献中包含小标 $i$ 的提取出来，就变成了只和 $i$ 相关的贡献：

• ${\sum }_{j\in S}cnt[j][i]\times po{s}_i$
• ${\sum }_{j\notin S}cnt[j][i]\times (-po{s}_i)$

这就是 $i$ 的贡献了，可以发现：把所有字母的贡献加起来，一定是这个放置顺序的答案

我们只需要从贡献这个角度切入就可以很容易得出状压 $DP$ 的转移

时间复杂度：$O(m^2\cdot 2^m)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

const int M = 21;

int cnt[M][M];
int dp[1 << M];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::string s;
    std::cin >> s;
    fore(i, 1, n){
        ++cnt[s[i] - 'a'][s[i - 1] - 'a'];
        ++cnt[s[i - 1] - 'a'][s[i] - 'a'];
    }
    memset(dp, INF, sizeof(dp));
    dp[0] = 0;
    fore(S, 0, 1 << m)
        fore(i, 0, m)
            if(!(S >> i & 1)){
                int nS = S | 1 << i;
                int res = 0;
                int pos = __builtin_popcount(S);
                fore(j, 0, m){
                    if(i == j) continue;
                    if(S >> j & 1) res += cnt[i][j] * pos;
                    else res -= cnt[i][j] * pos;
                }
                dp[nS] = std::min(dp[nS], dp[S] + res);
            }
    std::cout << dp[(1 << m) - 1];
    return 0;
}