题目描述

难度分:$2200$

输入$n(1 \leq n \leq 10^5)$，$m(1 \leq m \leq 20)$和长为$n$的字符串$s$，由前$m$ 个小写字母组成。

你需要构造一个长为$m$的小写字母排列，例如$m=3$时的$bac$，把这个排列当成一个只有一排的键盘。

在只用一根手指的情况下，用这个键盘打出$s$。

问：构造一个怎样的键盘，可以使手指的移动距离之和最小？输出这个最小值。

输入样例$1$

6 3
aacabc

输出样例$1$

5

输入样例$2$

6 4
aaaaaa

输出样例$2$

0

输入样例$3$

15 4
abacabadabacaba

输出样例$3$

16

算法

状压DP

看到$m$这么小就很想用状压DP，用一个$m$位二进制数$mask$来表示当前键盘上已经存在的字母，如果$mask$的第$i$位为$1$，就说明字母表的第$i$个字母是在键盘上的。因此，我们希望求得的就是$dp[2^m-1]$，刚好就表示所有的$m$个字母都装填到键盘上时，要敲出$s$串所需要的最小移动代价。

状态定义

$dp[mask]$表示当键盘状态为$mask$时用到所有字母的最小代价，在这个定义下答案就应该是$dp[2^m-1]$。

状态转移

这时候发现一个问题，就是我们只知道键盘上有哪些字母，但键盘上字母的排布我们是不知道的，所以也不知道具体的代价。因此，我们希望每装填进去一个字母就能直接统计出它的所有贡献。

可以预处理出一个$cnt$数组，$cnt[x][y]$表示$x$和$y$两个字母在$s$串中相邻的次数，这里面不关心$x$和$y$的相对顺序，是相邻就行。每当加入一个字母$i$，就会使得所有相邻且一个装了一个没装的字母对距离加一，统计出这个代价$cost=\Sigma_{i,j}cnt[i][j]$，$i$和$j$在$s$串中是相邻的，且一个已经加入键盘，另一个没有加入键盘。有了这个代价$cost$就可以$O(m^2)$进行单次状态转移了，详见代码。

复杂度分析

时间复杂度

状态数量为$O(2^m)$，单次转移的时间复杂度为$O(m^2)$，因此整个算法的时间复杂度为$O(m^22^m)$。

空间复杂度

空间消耗一方面来自于相邻字母对的频数统计数组$cnt$，空间消耗为$O(\Sigma^2)$，其中$\Sigma$表示字符集大小，本题中$\Sigma=26$。另一方面来自DP矩阵，它要记录$2^m-1$个状态的DP值，因此空间消耗为$O(2^m)$。因此，整个算法的额外空间复杂度为$O(\Sigma^2+2^m)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
char s[N];
int n, m, cnt[30][30], dp[1<<20];

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i < n; i++) {
        cnt[s[i + 1] - 'a'][s[i] - 'a']++;
        cnt[s[i] - 'a'][s[i + 1] - 'a']++;
    }
    dp[0] = 0;     // 初始时键盘为空
    for(int mask = 1; mask < (1<<m); mask++) {
        int cost = 0;
        dp[mask] = 0x3f3f3f3f;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) {
                if((mask>>i&1)^(mask>>j&1)) {
                    // i或j在键盘上
                    cost += cnt[i][j];
                }
            }
        }
        for(int i = 0; i < m; i++) {
            if(mask>>i&1) {
                dp[mask] = min(dp[mask], dp[mask^(1<<i)] + cost);
            }
        }
    }
    printf("%d\n", dp[(1<<m) - 1]);
    return 0;
}