题意

给出长为n的字符序列，集合大小为m，要求给字符编号（即一种m的排列），定义代价为相邻字符编号差的绝对值，求最小代价

题解

状压dp
不妨设按照1~m的顺序给字符编号，每次确定一个字符，代价为它到之间已经确定的字符的代价和
但是，我们无法保留确定的顺序，如何求解？

不妨假设所有字符一开始标号均为1，那么，当编号1确定时，将其他编号都设为2，当编号2确定时，将没确定的都设为3，以此类推
每确定一个编号的过程，代价更新，就是，已确定的和尚未确定的两两代价之和
例如 abcd
当确定a为编号1时，那么 bcd的编号距离a至少为1，所以要加上 a-b,a-c,a-d的代价
当确定b为编号2时，那么cd的编号距离a至少为2，距离b至少为1，所以加上b-c,b-d的代价
有因为上次加过a到其他字符的代价，这次新增加的距离为1，所以加上 a-c,a-d的代价
当确定c为编号3时，那么d的编号距离a至少为3，距离b至少为2，距离c至少为1，新增加的代价都是1，所以，加上 a-d,b-d,c-d的代价

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef  pair<int,int> pp;

int cnt[40][40];

int f[1<<20];
char ch[N];

int main(int argc, char const *argv[])
{
    int n,m;
    scc(n,m);
    scanf("%s",ch);
    for(int i=1;i<n;i++) cnt[ch[i]-'a'][ch[i-1]-'a']++,cnt[ch[i-1]-'a'][ch[i]-'a']++;
    fill(f,f+(1<<m),INF);
    f[0]=0;
    int tot=1<<m;
    for(int i=1;i<tot;i++){
        int tmp=0;
        for(int j=0;j<m;j++) if (i>>j&1)
            for(int k=0;k<m;k++) if (!(i>>k&1)) tmp+=cnt[j][k];
        for(int j=0;j<m;j++) if (i>>j&1)
            f[i]=min(f[i],f[i^(1<<j)]+tmp);
    }
    cout<<f[tot-1];
    return 0;
}