题解 | dd爱捣乱

tommy 第一次在这个网站上发 $\texttt{Editorial}$ （逃

题意

将一个串变成完美串的最小编辑代价，其中将字符 $a$ 编辑为字符 $b$ 的代价为 $\min(|a-b|,26-|a-b|)$ ，完美串的定义为任意长度 $\geq 2$ 的子串都不为回文串。

解法

做过 $\text{K-palindrome}$ 这题的可能会立刻发现，任何一个回文串都是有对称中心的，对称中心对应了两种基本串：长度为 $2$ 和长度为 $3$ 的回文串。只要整个字符串中不存在这两种串，那么这个字符串中就不存在任意长度 $\geq 2$ 的回文串。

于是想到 $\text{DP}$ ，定义状态为 $f[i,\alpha,\beta]$ 表示前 $i$ 个字符，第 $i$ 个字符为 $\alpha$ ，第 $j$ 个字符为 $\beta$ 的最小编辑代价。但是状态数是 $O(nT^2)$ 的，其中 $T=26$ 为字符集大小。

观察一下，发现如果修改一个字符，其代价一定不会超过 $2$ 。因为代价不超过 $2$ 的有 $4$ 个字符，在能修改的情况下我们肯定尽可能希望代价最小。不妨优化状态定义，设 $f[i,\alpha,\beta]$ 为前 $i$ 个字符，修改后第 $i$ 个字符与 $s_i$ 的距离为 $\alpha$ ，第 $i-1$ 个字符与 $s_{i-1}$ 的距离为 $\beta$ 。通过修改状态定义，状态数缩减至 $O(25n)$ 。

滚动数组后总空间复杂度可优化至 $O(n+50)$ 。

代码

#include<cstdio>
#include<cstring>
#define register  
char s[1000005];
int f[5][5],tmp[5][5];
inline int abs(const int &x) {
    return x<0? -x:x;
}
inline int min(const int &x,const int &y) {return x<y? x:y;}
int main() {
    int n;
    scanf("%d%s",&n,s+1);
    for(register int j=0;j<5;++j) {
        for(register int k=0;k<5;++k) {
            f[j][k]=0x3f3f3f3f;
        }
    }
    for(register int i=-2;i<=2;++i) {
        f[i+2][0]=abs(i);
    }
    for(register int i=1;i<n;++i) {
        for(register int j=0;j<5;++j) {
            for(register int k=0;k<5;++k) {
                tmp[j][k]=0x3f3f3f3f;
            }
        }
        for(register int j=-2;j<=2;++j) {
            for(register int k=-2;k<=2;++k) {
                for(register int l=-2;l<=2;++l) {
                    if((j+s[i+1]+26)%26==(k+s[i]+26)%26) continue;
                    if(i>1&&((j+s[i+1]+26)%26==(l+s[i-1]+26)%26)) continue;
                    tmp[j+2][k+2]=min(tmp[j+2][k+2],f[k+2][l+2]+abs(j));
                }
            }
        }
        for(register int j=0;j<5;++j) {
            for(register int k=0;k<5;++k) {
                f[j][k]=tmp[j][k];
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(register int i=0;i<5;++i) {
        for(register int j=0;j<5;++j) {
            ans=min(ans,f[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}