动态规划

设$dp_{i,j}$为前i个字符相邻字符不相同且第i个字符操作j次的最小次数$\\$ 每一个字符串最多变化26次，在多的话就是浪费操作次数了遍历到i,j的时候去匹配前1个字符的变化的k次情况取最小值即可$\\$ dp方程$\\$

1. i=1 dp[i][j]=min(dp[i][j],dp[i-1][k]+j)$\\$
2. i!=1&&第i个字符操作j次!=第i-1个字符操作k次 dp[i][j]=min(dp[i][j],dp[i-1][k]+j); $\\$

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
int mx=INT_MAX;
int dp[N][30];//dpij表示第i个字母变成操作j次后变成合法性次数
int a[N];
int check(int x1,int w1,int x2,int w2){
	return ((x1+w1)%26)!=((x2+w2)%26);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	char c='z'+1;
	s=' '+s;
	for(int i=1;i<=n;i++){
		a[i]=s[i]-'a';		
	}
	for(int i=0;i<=26;i++){
		dp[0][i]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=26;j++){
			dp[i][j]=mx;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=26;j++){
			for(int k=0;k<=26;k++){
				if(check(a[i-1],k,a[i],j)||i==1){
					dp[i][j]=min(dp[i][j],dp[i-1][k]+j);
				}
			}
		}
	}
	int ans=mx;
	for(int i=0;i<=26;i++){
		ans=min(ans,dp[n][i]);
	}
	cout<<ans<<'\n';
	return 0;
}

题目内容

小红有一个长度为$n$的字符串$S$，现在他可以执行以下的操作：

选择一个索引$i$($1≤i≤n$)，并将$S_i$按照字母表上的顺序、循环右移一位。例如：‘$a$’右移一位为‘$b$’，‘$z$’右移一位为‘$a$’。

小红想知道使得字符串$S$任意两个相邻的字符都不一致的最小操作次数为多少。

输入描述

第一行输入一个整数 $n$($2≤n≤10^5$)代表字符串的长度。

第二行输入一个长度为$n$，且只包含小写字母的字符串$S$。

输出描述

在一行输出$n$个整数，代表使得任意两个相邻的字符都不一致的最小操作次数。

样例1

输入

3
aaa

输出

1

说明

只需要将第二个‘$a$’右移一位即可。

样例2

输入

2
ab

输出

0