C++ 解法, 执行用时: 314ms, 内存消耗: 99268K, 提交时间: 2021-05-28 22:50:45

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,dp[N][5][5],res=1e9; char str[N];
inline char get(char a,int x){return ((a-'a'+(x>=3?x-5:x))+26)%26+'a';}
inline int val(int x){return x>=3?5-x:x;}
signed main(){
	scanf("%d %s",&n,str+1);
	memset(dp,0x3f,sizeof dp);
	for(int i=0;i<5;i++) for(int j=0;j<5;j++) dp[1][i][j]=val(j);
	for(int i=2;i<=n;i++)
		for(int j=0;j<=4;j++)
			for(int k=0;k<=4;k++)
				for(int s=0;s<=4;s++){
					char c0=get(str[i],j),c1=get(str[i-1],k),c2=get(str[i-2],s);
					if(c0!=c1&&c0!=c2&&c1!=c2)	dp[i][k][j]=min(dp[i][k][j],dp[i-1][s][k]+val(j));
				}
	for(int i=0;i<=4;i++) for(int j=0;j<=4;j++)	res=min(res,dp[n][j][i]);
	cout<<res;
	return 0;
}