E. Keyboard Purchase

トランスファゲート
$m$は$20$しかないことに気づいて、状圧$dp$を考えてみましょう.
$f[S]$が現在決定されている文字セットを$S$とすると、転送は、右端から加わる次の文字$c$を考慮する.
それでは問題が来て、代価はどのように計算します
1文字を追加するたびに、すべての文字間の移動$(c_i,c_{i+1})$に対する代価を考慮します.
では明らかに$c_i\in S$ ,$c_{i+1}otin S$を移動すると、$(c_i,c_{i+1})$が現在追加されている文字の位置を多く通過し、必要な時間が$1$増加します.
$cnt[i][j]$は$cを表すように維持できます{i}=i,c_{i+1}=j$の移動数
では、転送のたびに$m^2$を直接すべての$c_を列挙することができます.{i}\in S$ ,$c_{i+1}otin S$の移動求め
この複雑さは$m^2cdot 2^m$計算すると$4cdot 10^8$レベルに達し、時間制限$1 s$に達していることが明らかに問題があります.
では、代価を計算する速度を最適化したり、信仰で複雑度の悪いコードを直接渡したりする2つの選択肢があります.
そしてあなたは信仰が正しいことに気づいて、期限を押さえて过ごすことができます....例えばこの神様:https://codeforces.com/contest/1238/submission/62149786
4点$997 ms$1点$998 ms$text{Orz}$
でも信じてない
コストを迅速に計算する方法を考えて、$h[S]$をすべての$c_を表すようにします.i\in S$ ,$c_{i+1}otin S$の移動数
さらに$g[p][S]を設定し、p otin S$は$cを表す.i=p , c_{i+1}in S$の移動数
では$h[S]=sum_{pin S}g[p][Utext{^}S]$,そのうち$U$は全話
$g$の計算を考えてみましょう.$pごとに、S$がすべての$p'otin S$の再累積を列挙するのは明らかに遅すぎます.
$S$のサブセット$S'$の代価$g[p][S']$が必ず$g[p][S]$に加わることに注意すると、$S$に対して選択された$p'$を直接列挙する
$S'|(1<有$g[p][S]=g[p][S']+cnt[p][p']$
そして今、すべての$S$に対して$1$の位置を求める小さな問題があります.
ツリー配列の動作を考慮すると、$x&-x$は$x$の最初の$1$の値です.
最終メンテナンス$pos[x]$表現値は$x=(1<
そしてこの問題は解決し、複雑度$O(mcdot 2^m)$

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=1e5+7,M=20;
int n,m,cnt[M][M];
int pos[(1<7],f[(1<7],g[M][(1<7],h[(1<7];
char s[N];
vector <int> V[M];
int main()
{
    n=read(),m=read();
    scanf("%s",s+1);
    for(int i=1;i)
        cnt[s[i]-'a'][s[i+1]-'a']++,
        cnt[s[i+1]-'a'][s[i]-'a']++;
    for(int i=0;i1<i;
    memset(f,0x3f,sizeof(f));
    int mx=(1<1; f[0]=0;
    for(int p=0;p)
        for(int o=1;o)
        {
            if(o&(1<
continue;
            g[p][o]=g[p][o-(o&-o)]+cnt[p][pos[o&-o]];
        }
    for(int o=0;o)
        for(int p=0;p)
            if(o&(1<
o];
    for(int o=0;o)
        for(int p=0;p)
        {
            if(o&(1<
continue;
            f[o^(1<
1<
h[o]);
        }
    printf("%d
",f[mx]);
    return 0;
}