Codeforces 1238E. Keyboard Purchase状压dp

Codeforces 1238E. Keyboard Purchase
每一个字母都对答案由两种影响
①加②减分别是他相对于他前面对答案的影响和他对于他后面对答案的影响
复杂对为2^m*（m*m） 大概在4e8左右
可以优化成1e8
__builtin_popcount（i） 求i的二进制里1的个数

#include<bits/stdc++.h>
using namespace std;
typedef long long L;
char s[100100];
int dp[2000010];
int mp[32][32];
int main()
{//cout<<INT_MAX<<endl;
    //cout<<(1<<(20));
    int n,m;
    scanf("%d %d",&n,&m);
    scanf("%s",s);
    for(int i=1; i<n; i++)
    {
        int u=s[i]-'a'+1;
        int v=s[i-1]-'a'+1;
        if(u==v) continue;
        mp[u][v]++;
        mp[v][u]++;
    }
    memset(dp,0x3f,sizeof dp);

    dp[0]=0
    //fill(dp+1,dp+(1<<m),INT_MAX);
    int len=(1<<m);
    //for(int i=0;i<=len;i++) dp[i]=0x3f3f3f;
    for(int i=0; i<len; i++)
    {
        int c=__builtin_popcount(i);
        for(int j=1; j<=m; j++)
        {
            int tmp=dp[i];
            if(!(i&(1<<(j-1))))
            {
                for(int k=1; k<=m; k++)
                {
                    if(i&(1<<(k-1)))
                    {
                        tmp+=mp[j][k]*c;
                    }
                    else
                    {
                        tmp-=mp[j][k]*c;
                    }
                }
                dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],tmp);
            }
        }
    }
    printf("%d\n",dp[len-1]);
}