题目链接：点我啊╭(╯^╰)╮
题目大意：
长度为 n ≤ 1 e 5 n≤1e5 n≤1e5 的串，字符集为 m ≤ 20 m≤20 m≤20
键盘上有对应的 m m m 个键，排成一排
键位自定义，问输出这个串的最短总和距离为多少？？
解题思路：
m m m 只有 20 20 20， 考虑状压
设 c n t [ x ] [ y ] cnt[x][y] cnt[x][y] 为字母 x x x 到 y y y的总次数
d p [ s ] dp[s] dp[s] 为状态为 s s s 时，已经将 s s s 每个状态位的字符放到键盘上，移动的最少距离
接下来考虑距离的影响
考虑每次转移时，新的字母 x x x 放到键盘的最右边，设 p o s [ x ] pos[x] pos[x] 为 x x x 在键盘上的位置
则从 d p [ s ] ? > d p [ s ∣ 1 < < x ] dp[s] -> dp[s | 1<<x] dp[s]?>dp[s∣1<<x]，要考虑 x x x 到 s s s 里的字母里的距离 与 x x x 到 s s s 外的字母里的距离
∑ k ∈ S c n t [ x ] [ k ] × ( p o s [ x ] ? p o s [ k ] ) + ∑ k ? S c n t [ x ] [ k ] × ( p o s [ k ] ? p o s [ x ] ) \sum_{k\in S}{cnt[x][k] \times (pos[x] - pos[k])} + \sum_{k\notin S}{cnt[x][k] \times (pos[k] - pos[x])} ∑k∈S?cnt[x][k]×(pos[x]?pos[k])+∑k∈/?S?cnt[x][k]×(pos[k]?pos[x])
每次转移需要计算 S S S 状态下，上式的值，发现可以预处理
预处理的是每个 S S S 的每个状态位与每个非状态位的距离总和 d [ S ] d[S] d[S]
那么转移的时候从 d p [ s ] ? > d p [ s ∣ 1 < < x ] ， d p [ s ∣ 1 < < x ] = m i n （ . . . ， d p [ s ] + d [ s ] ） dp[s] -> dp[s | 1<<x]，dp[s | 1<<x] = min（...，dp[s] + d[s]） dp[s]?>dp[s∣1<<x]，dp[s∣1<<x]=min（...，dp[s]+d[s]）
这样通过每次转移，都处理了键盘里的字母与非键盘里的字母的距离
时间复杂度： O ( m 2 × 2 m + m × 2 m ) O(m^2 \times 2^m + m \times 2^m) O(m2×2m+m×2m)
达到了 4 e 8 4e8 4e8，很明显 c f cf cf 是可以卡过的，但考虑更优的做法的话
对于 ∑ k ∈ S c n t [ x ] [ k ] × ( p o s [ x ] ? p o s [ k ] ) + ∑ k ? S c n t [ x ] [ k ] × ( p o s [ k ] ? p o s [ x ] ) \sum_{k\in S}{cnt[x][k] \times (pos[x] - pos[k])} + \sum_{k\notin S}{cnt[x][k] \times (pos[k] - pos[x])} ∑k∈S?cnt[x][k]×(pos[x]?pos[k])+∑k∈/?S?cnt[x][k]×(pos[k]?pos[x])
因为 p o s [ x ] = = S pos[x] == S pos[x]==S 里的 1 1 1 的个数，但 p o s [ k ] pos[k] pos[k] 未知，如果考虑 p o s [ k ] pos[k] pos[k] 则会到达 m 2 × 2 m m^2 \times 2^m m2×2m
这里我们只考虑插入字母 x x x 时， p o s [ x ] pos[x] pos[x] 对转移的影响
则上式变为： ∑ k ∈ S c n t [ x ] [ k ] × p o s [ x ] ? ∑ k ? S c n t [ x ] [ k ] × p o s [ x ] \sum_{k\in S}{cnt[x][k] \times pos[x]} - \sum_{k\notin S}{cnt[x][k] \times pos[x]} ∑k∈S?cnt[x][k]×pos[x]?∑k∈/?S?cnt[x][k]×pos[x]
这样我们在预处理时，设 d [ s ] [ x ] d[s][x] d[s][x] 为 x ? s ， ∑ k ∈ s c n t [ x ] [ k ] x \notin s，\sum_{k \in s}{cnt[x][k]} x∈/?s，∑k∈s?cnt[x][k]
发现 d [ s ] [ x ] d[s][x] d[s][x] 也可以通过子集的状态转移，设 i ∈ s i \in s i∈s
d [ s ] [ x ] = d [ s d[s][x] = d[s d[s][x]=d[s ^ i ] [ x ] + c n t [ x ] [ i ] i][x] + cnt[x][i] i][x]+cnt[x][i]
只需要知道一个 i ∈ s i \in s i∈s，考虑树状数组里的 s & ? s s \& {-s} s&?s 则可以得到 s s s 里的最低位的 1 1 1
预处理之后， d p dp dp 的转移则要考虑位置的影响
d p [ n s ] = m i n ( d p [ n s ] , d p [ s ] + p o s [ x ] ? ( d [ s ] [ x ] ? d [ ( ( 1 < < m ) ? 1 ) dp[ns] = min(dp[ns], dp[s] + pos[x] * (d[s][x] - d[((1<<m)-1) dp[ns]=min(dp[ns],dp[s]+pos[x]?(d[s][x]?d[((1<<m)?1) ^ n s ] [ x ] ) ) ns][x])) ns][x]))
那么问题来了，为什么只考虑 p o s [ x ] pos[x] pos[x] 对转移的影响，而不考虑 p o s [ k ] pos[k] pos[k] 的影响？
观察 ∑ k ∈ S c n t [ x ] [ k ] × ( p o s [ x ] ? p o s [ k ] ) ? ∑ k ? S c n t [ x ] [ k ] × ( p o s [ k ] ? p o s [ x ] ) \sum_{k\in S}{cnt[x][k] \times (pos[x] - pos[k])} - \sum_{k\notin S}{cnt[x][k] \times (pos[k] - pos[x])} ∑k∈S?cnt[x][k]×(pos[x]?pos[k])?∑k∈/?S?cnt[x][k]×(pos[k]?pos[x])
发现对于 p o s [ k ] pos[k] pos[k]，在不断的转移计算过程中，最终会全部抵消掉，总和为 0 0 0
也就是 p o s [ k ] pos[k] pos[k] 对最终答案是没用影响的
那么现在的状压 d p dp dp 所表示的就不是原本的状压了，中间的过程状态都是错的
但最终的结果是正确的的（QwQ ~~~）
时间复杂度： O ( m × 2 m ) O( m \times 2^m) O(m×2m)
核心：预处理状态转移，子集优化dp
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m, cnt[25][25];
int d[1<<21][25], dp[1<<21];
char s[maxn];int main() {scanf("%d%d%s", &n, &m, s+1);for(int i=1; i<n; i++){cnt[s[i]-'a'][s[i+1]-'a']++;cnt[s[i+1]-'a'][s[i]-'a']++;}for(int s=1; s<1<<m; s++)for(int i=0; i<m; i++)d[s][i] = d[s & (s - 1)][i] + cnt[i][__builtin_ffs(s) - 1];memset(dp, 0x3f, sizeof(dp));dp[0] = 0;for(int s=0; s<1<<m; s++){for(int i=0; i<m; i++){if(1 << i & s) continue;int ns = 1 << i | s;int pos = __builtin_popcount(s);dp[ns] = min(dp[ns], dp[s] + pos * (d[s][i] - d[((1<<m)-1) ^ ns][i]));}}printf("%d\n", dp[(1<<m)-1]);
}