自动搬运

查看原文

来自洛谷，原作者为

	SDNetFriend 路漫漫其修远兮，吾将上下而求索 | AFO

搬运于2025-08-24 22:23:41，当前版本为作者最后更新于2022-03-09 11:19:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

转化

首先可以看出，那些 e 的位置对答案的贡献是固定的。当我们走到一段连续的 e 的前方，便可以后退一次删一次，如此反复，每个 e 的贡献就固定是 $2$，那么计算了这个之后把 e 从原序列剔除，并且我们把每一个左边有 e 的位置都标记为关键点，因为这些点必须经过才能删除 e。

于是问题变为了：可以花费 $1$ 的代价向左走一步，可以花费 $2$ 的代价跳到右边下一个任意字符，且序列中有若干关键点必须经过，求最小代价。

简化

根据官方题解或者感性理解或者经过严谨证明，可以得知最终的路线一定是向右跳若干步，然后向左走一段，然后继续向右跳。并且任何两段向左走的区间都不可能有交，否则一定不优。于是就像很多题解所写的那样，路径一定长成这样：（从博客园 cjoier_Itst 大佬处借了个图）

这就变成了一个“序列上的复杂路径”，考虑用线头 DP 解决。

动态规划

我们给路径切片，第 $i$ 片表示从 $i$ 到 $i+1$ 的路径片。然后观察这个图，发现只有两种路径片：被覆盖一次的和被覆盖三次的。这里的“覆盖”不一定是走到了这个点，一次向右跳过程中，中间经过的所有的点都算被覆盖的点，其实也就是长成这样：（竖线代表一个点）

最终我们的路径是由一片片这样的路径片拼起来形成的，我们实际上就是在决策第 $i$ 个位置到第 $i+1$ 个位置的路线变化情况，这些变化是在第 $i$ 个位置发生的。。

我们考虑设状态分别为 $f_{i,x}$ 和 $g_{i,x,y}$。

分别表示：考虑完前 $i$ 个路径片，当前路径片只被覆盖了一次（即右图），此次跳跃终点的字符是 $x$ 的最小代价；考虑完前 $i$ 个路径片，当前路径片被覆盖了三次（即左图），上方跳跃终点是 $x$，下方跳跃终点是 $y$ 的最小代价，详细点的话，一次跳跃-折返-跳跃的过程是被描述成了这种形式：

我们叫第一次跳跃为上方跳跃，第二次为下方跳跃（即两条绿色的曲线）。

注意这个绿色曲线不一定只跳了一次，可能是由很多次跳跃组成的。

那我们又怎么计算代价呢？考虑有几种边界情况：

（只画出了一部分情况）。

就是说，对向右跳这个过程，存在“起跳”和“降落”的位置，而我们考虑只在起跳的位置把贡献加上去就可以了。

通俗一点讲，我们以第一张图为例，假设现在的情况是：

左边是第 $i$ 个路径片，右边是第 $i+1$ 个，三条竖线分别代表 $i,i+1,i+2$。我们设 $s_i$ 表示 $i$ 位置的字符。考虑什么时候会出现这种情况，出现了又要如何计算贡献。

当且仅当第 $i$ 个路径片，对应的状态是 $f_{i,s_{i+1}}$，那么因为向右跳是跳到第一个对应字符的位置，所以在 $i+1$ 的位置就必须降落，并重新起跳。那么这次新的起跳就会产生 $2$ 的代价。（当然如果你把贡献在降落位置计算是完全没有问题的）

以此类推，这个题就可以 DP 了，转移方程：（$flg_i$ 表示 $i$ 是关键点）

$$\begin{aligned} f_{i-1,x}\to f_{i,x} && flg_i=F,x\neq s_i\\ f_{i-1,s_i}+2\to f_{i,x}\\ g_{i-1,s_i,x}\to f_{i,x} && x\neq x_i\\ g_{i-1,s_i,s_i}+2\to f_{i,x} \end{aligned} $$

以上是对 $f_{i,x,y}$ 的转移，分别表示：

• 没降落也没起跳，只被覆盖一次，因为 $i$ 不会被经过所以不能是关键点 。
• 在当前位置降落了，并继续向 $x$ 去跳。
• 第 $i-1$ 片被覆盖了三次，并且其对应的上方（就是设计状态那个上）跳跃的终点位置在 $i$。
• 第 $i-1$ 片被覆盖了三次，并且其对应的上方下方的跳跃终点位置都在 $i$，此时需要从 $i$ 处接着下方跳跃起跳。

$$\begin{aligned} g_{i-1,x,y}+1\to g_{i,x,y} && x\neq s_i, y\neq s_i\\ g_{i-1,x,s_i}+3\to g_{i,x,y} && x\neq s_i\\ g_{i-1,s_i,y}+3\to g_{i,x,y} && y\neq s_i\\ g_{i-1,s_i,s_i}+5\to g_{i,x,y}\\ f_{i-1,s_i}+5\to g_{i,x,y}\\ f_{i-1,x}+3\to g_{i,x,y} && x\neq s_i \end{aligned} $$

以上是对 $g_{i,x,y}$ 的转移，分别表示：

• 上下两个跳跃都没降落也没起跳，向左走的那一步产生了 $1$ 的贡献，接下来的每一个状态都有向左走的 $1$ 的贡献。
• 下方跳跃在点 $i$ 降落并重新起跳，额外产生 $2$ 的贡献。
• 上方跳跃在点 $i$ 降落并重新起跳，额外产生 $2$ 的贡献。
• 上下方跳跃都在 $i$ 降落并重新起跳，额外产生 $4$ 的贡献。
• 第 $i-1$ 片被覆盖了一次，并且其在 $i$ 处降落，所以上方从 $i$ 起跳产生了 $2$ 的贡献，因为左侧只被覆盖一次，所以下方跳跃也从 $i$ 起跳，再次产生 $2$ 的贡献。
• 第 $i-1$ 片只被覆盖了一次，并且上方跳跃没有降落。此时 $i$ 会作为下方跳跃的起点，产生 $2$ 的贡献。

知道这些就可以愉快地 DP 了。初始我们设 $f_{0,s_1}=0$，然后最终我们假设在无限远的地方有一个没有出现过的字符，可以认为是 k，使最后一次起跳终点为 k，那我们这部分的答案就是 $f_{n,k}-2$，因为最后一次实际上并没有起跳。

代码

转移顺序和上述一致。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	char c;int f=1,res=0;
	while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res*f;
}
const int N=7e4+5,A=10;
int n,a[N],ans0,ans;
char s[N];bool flg[N];
inline void init(){
	int lst=0,_n=0;
	for(int i=1;i<=n;++i){
		if(s[i]!='e'){
			a[++_n]=(s[i]>'e'?s[i]-'a'-1:s[i]-'a');
			if(lst)flg[_n]=true,lst=0;
		}else ans0+=2,lst=i;
	}n=_n;
}int f[2][A],g[2][A][A];
inline void umin(int &x,int y)
	{if(y<x)x=y;}
inline void solve(){
	memset(f,0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	f[0][a[1]]=0;	
	for(int i=1;i<=n;++i){
		swap(f[0],f[1]);swap(g[0],g[1]);
		memset(f[0],0x3f,sizeof f[0]);
		memset(g[0],0x3f,sizeof g[0]);
		int c=a[i];
		for(int x=0;x<A;++x){
			if(!flg[i]&&x!=c)umin(f[0][x],f[1][x]);
			umin(f[0][x],f[1][c]+2);
			if(x!=c)umin(f[0][x],g[1][c][x]);
			umin(f[0][x],g[1][c][c]+2);	
		}
		for(int x=0;x<A;++x)
			for(int y=0;y<A;++y){
				if(x!=c&&y!=c)umin(g[0][x][y],g[1][x][y]+1);
				if(y!=c)umin(g[0][x][y],g[1][c][y]+3);
				if(x!=c)umin(g[0][x][y],g[1][x][c]+3);
				umin(g[0][x][y],g[1][c][c]+5);
				umin(g[0][x][y],f[1][c]+5);
				if(x!=c)umin(g[0][x][y],f[1][x]+3);
			}
	}ans=f[0][A-1]-2;
}
int main(){
	freopen("vim.in","r",stdin);
	freopen("vim.out","w",stdout);
	n=read();scanf("%s",s+1);
	init();solve();
	printf("%d",ans0+ans);
	return 0;
}