codeforces 1238 E

题解妙！
和之前出的那道状压dp差不多啊怎么这个我就不会呢...

发现我们只需要考虑贡献就行了，对于新加入的字母，它与已加入的所有数字的距离都会加一，与未加入的所有的数字都会减一，
也可以认为，对于所有已加入的数字和未加入的数字，他们的距离增加了一

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;string s;
int a[20][20];
ll dp[1048576];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        a[s[i]-'a'][s[i-1]-'a']++;
        a[s[i-1]-'a'][s[i]-'a']++;
    }
    for(int i=0;i<(1<<m);i++)dp[i]=1e18;
    dp[0]=0;
    for(int i=0;i<(1<<m);i++){
        vector<int> d,f;
        for(int j=0;j<m;j++)if(i>>j&1)d.push_back(j);else f.push_back(j);
        ll tmp=0;
        for(int k=0;k<d.size();k++){
            for(int g=0;g<f.size();g++){
                tmp+=a[d[k]][f[g]];
            }
        }
        for(int j=0;j<m;j++){
            if(i>>j&1)continue;
            dp[i|1<<j]=min(dp[i|1<<j],dp[i]+tmp);
        }
    }
    cout<<dp[(1<<m)-1]<<endl;
}

codeforces 1238 E

原文：https://www.cnblogs.com/MXang/p/11660353.html