搞了一个 (nk^2) 的做法。
首先如果前面是一个 (e) 那下一步一定是将 (e) 删掉，花费 $2$ 。
那么可以将 (e) 删掉，每个之前有 (e) 的点都必须经过，求最短的方案。
答案一定是向后走一段，然后把前面的所有必经点都走掉，于是可以轻松得到 (O(n^2)) 的做法。
现在考虑优化。
很容易想到的是每次只向后走一个，然后立即将前面所有必经点走掉。如果这个结论正确那状态是 (nk) 的，很容易转移。
然而需要注意这里向后走的费用是 $2$，于是类似：
[
egin{aligned}
&ca dots aaba\
&01 dots 1011
end{aligned}
]
这样的数据可以卡掉。
但是我们可以考虑一个更平凡的结论：
- 考虑每次向后一段再向前，再向后一次，最终到达的那一个节点一定是第一次到达。
证明：例如：
[ egin{matrix} a & o & o & b & o & c \ & d & leftarrow &leftarrow &leftarrow&leftarrow \ & & o & o &e end{matrix} ]我们显然可以改为：
[ egin{matrix} a & o & o & b & & c \ & d & leftarrow & && \ & o & o & o &e \ & & & b+1 & leftarrow \ & & & o& o & c end{matrix} ]这样的话可以发现答案变小。
于是最终答案一定可以分为若干段，每一段从左边一直跳到右边，然后退回左边，并且两段之间无交。
于是我们考虑以下状态： (f(i,j)) 表示当前在 (i)，已经从 (j) 走到 (i) 的答案。
(g(i,j)) 表示当前在 (j)，上一段的最右端是 (i) 的答案。
我们每次改变较小的还要改变的位置。
考虑转移有哪些：
第一种是 (f(i,j) o g(j, ext{next}(i))) 即下一段第一个经过的是 (j) 。
第二种是 (g(i,j) o f( ext{first}(i+1,j),j)) 即下一段退回到 (i+1,j) 这段的第一个必经点。
第三种是 (g(i,j) o g( ext{next}(i),j)) 即上一段延长了。
不难发现 (j) 就是 (i) 或者 (i) 的后继节点，于是状态是 (nk) 的，转移 (O(k)) ，于是总复杂度 (O(nk^2))。
需要注意特判以下最后一段以及 (i=j) 的转移。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 7e4+5;
const int table[10]={0,1,2,3,-1,4,5,6,7,8};
int n;char s[N];
bool mark[N];
int ch[N],nxt[N][9],Last[N],f[N][9],g[N][9],Mark[N],h[N];
int ans=0x3f3f3f3f;
inline void Doit(int S){
for(int y=0;y<9;y++)if(nxt[S][y]&&f[S][y]!=0x3f3f3f3f){
if(Mark[nxt[S][y]+1]==0){
ans=min(ans,f[S][y]);continue;
}else{
for(int j=0;j<9;j++)if(nxt[nxt[S][y]+1][j]){
int ny = nxt[nxt[S][y]+1][j];
ans=min(ans,f[S][y]+h[ny]+ny-nxt[S][y]);
}
}
for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
int to1=nxt[S][y], to2=nxt[S+1][y2];
if(to2>=to1){
int nxt = Mark[to1+1];nxt=min(nxt,to2);
f[nxt][y2]=min(f[nxt][y2],to2-nxt+f[S][y]+2);
}
//if(to2<=to1) f[to2][y]=min(f[to2][y],2+f[S][y]);
}
int to1=nxt[S][y];
if(to1==S){
for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
for(int y3=0;y3<9;y3++)if(nxt[S+1][y3]){
int to2=nxt[S+1][y2],to3=nxt[S+1][y3];
if(to2<to3)g[to2][y3]=min(g[to2][y3],f[S][y]+2+2+to2-S);
}
}
}
for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
int to2=nxt[S+1][y2];
if(to2>=to1)g[to1][y2]=min(g[to1][y2],f[S][y]+2);
}
}
for(int y=0;y<9;y++)if(nxt[S][y]&&g[S][y]!=0x3f3f3f3f){
for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
int to1=nxt[S][y], to2=nxt[S+1][y2];
if(to2<=to1)g[to2][y]=min(2+to2-S+g[S][y],g[to2][y]);
}
int _nxt=min(Mark[S+1],nxt[S][y]);
f[_nxt][y]=min(f[_nxt][y],g[S][y]+nxt[S][y]-_nxt);
}
}
int main()
{
cin >> n;
scanf("%s",s+1);
int _n=0;
int ans2=0;
for(int i=1;i<=n;i++){
if(s[i]=='e'){ans2+=2;continue;}
else ch[++_n]=table[s[i]-'a'],mark[_n]=s[i-1]=='e';
}
mark[1]=1;n=_n;
for(int i=n;i;i--){
Mark[i]=mark[i]?i:Mark[i+1];
Last[ch[i]]=i;
for(int j=0;j<9;j++)nxt[i][j]=Last[j];
}
for(int i=n;i;i--){
h[i]=0x3f3f3f3f;if(!Mark[i+1])h[i]=2;
for(int j=0;j<9;j++)if(nxt[i+1][j]){
int nx=nxt[i+1][j];
if(nx)h[i]=min(h[i],h[nx]+2+nx-i);
}
}
for(int i=1;i<=n;i++)for(int j=0;j<9;j++){g[i][j] = f[i][j] = 0x3f3f3f3f;}
f[1][ch[1]]=0;
for(int i=1;i<=n;i++)Doit(i);
cout << ans + ans2 << endl;
}