题解 CF1238E 【Keyboard Purchase】

whiteqwq · 2020-10-20 19:35:58 · 题解

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]);