CF1238E Keyboard Purchase解题报告

解题报告

CF1238E Keyboard Purchase解题报告：

更好的阅读体验

题意

• 给定一个长度为$n$的密码，且其由前$m$个小写字母组成；
• 在输入密码的过程中，你的手指需要在密码相邻的两个字母在键盘上的位置移动，缓慢度为这两个位置的距离；
• 对于一个键盘，输入密码的缓慢度为输入密码的缓慢度之和，请设计一个键盘，让缓慢度最小。
• 数据范围：$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 20$。

分析

状压dp。

看到这么小的$m$，我们就可以大概猜出要压这个$m$，于是套路的设计状态：$f_i$为设计的键盘（不需要设计完）用到的所有字母压缩起来是$i$的最小缓慢度。

但是有一个问题，对于这个状态，我们不能知道它字母的顺序，所以并不能统计答案。

我们要设计一种无后效性的dp：每一次装一个字母就直接统计出来它的所有贡献（费用提前思想）。

考虑装一个字母的贡献：会让所有相邻且一个装了一个没装的字母对距离加一，这样我们就可以快速地统计出来答案了。

设$cnt_{i,j}$为$i,j$相邻的状态数，很容易统计出来，然后就是套路的状压dp了。

代码

代码非常简短，记得开$\text{long long}$。

for(int i=1;i<n;i++)
    cnt[s[i]-96][s[i+1]-96]++,cnt[s[i+1]-96][s[i]-96]++;
st=(1<<m)-1;
f[0]=0;
for(int i=1;i<=st;i++){
    int sum=0;
    f[i]=inf;
    for(int j=1;j<=m;j++)
        for(int k=j+1;k<=m;k++)//不统计重复
            if(((i>>(j-1))&1)^((i>>(k-1))&1))//j在键盘上或k在键盘上
                sum+=cnt[j][k];
    for(int j=1;j<=m;j++)
        if((i>>(j-1)&1))
            f[i]=min(f[i],f[i^(1<<(j-1))]+sum);
}
printf("%lld\n",f[st]);