题解 | #爱丽丝的人偶圆舞曲#

一道不算难，但写起来有点难的dp。

记 为前 项中，最后一位一定为 的最小开销

显然 ，即第一个字符一定为第一个字符是不需要修改的。

而，即第一个字符如果要修改为别的字符，就是花费1个代价。

考虑如何转移，如果要考虑第 项改为，那前一项可以是 ，其中 是 符合和谐条件的两个字母，二者取一个最小值，然后加上第项改为的代价

现在我们并不知道步长，所以还需要外层额外枚举一次步长。

总时间复杂度是的，其中是字符集大小，这里 ,这里的空间复杂度达到了惊人的,由于每次枚举新的步长，都要重新设定数组，所以空间复杂度很难堪。

又借助熟悉的滚动数组方式，但是借助的 可能比当前大，也可能比当前小，所以没办法只优化成一维直接优化，但我们可以变成2个数组，一个代表前一项的，一个代表当前的，每次遍历一项后，就进行交换,这样做的空间复杂度是，也就是46个int的大小，内存占用名列前茅

其实还有个优化的点是，步长不必枚举到25，因为和谐有2种，在模26的意义上是两两成对的，只需要枚举到13就可以了

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=2e5+7;
const int M=1e9+7;
typedef long long ll;
typedef vector<int> vt;

string s;
int n;
int lst[26];
int cur[26];
int ans=0x3f3f3f3f;
void solve(){
   cin>>s;
   n=s.size();
   s=" "+s;
   for(int d=0;d<=25;d++){ //枚举步长
        memset(lst,0x3f3f3f3f,sizeof lst);
        for(int i=0;i<26;i++)lst[i]=(s[1]-'a'!=i);
        //初始化
        for(int i=2;i<=n;i++){
            memset(cur,0x3f3f3f3f,sizeof cur);
            for(int j=0;j<26;j++){ //若要把当前的修改成j
               int A=(j-d+26)%26;
               int B=(j+d)%26;
               cur[j]=min(cur[j],min(lst[A],lst[B])+(s[i]-'a'!=j));
            }
            for(int i=0;i<26;i++)lst[i]=cur[i];
        }
        for(int j=0;j<26;j++)ans=min(ans,lst[j]);
   }
   cout<<ans;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}