搞了一个 \(nk^2\) 的做法。

首先如果前面是一个 \(e\) 那下一步一定是将 \(e\) 删掉，花费 \(2\) 。

那么可以将 \(e\) 删掉，每个之前有 \(e\) 的点都必须经过，求最短的方案。

答案一定是向后走一段，然后把前面的所有必经点都走掉，于是可以轻松得到 \(O(n^2)\) 的做法。

现在考虑优化。

很容易想到的是每次只向后走一个，然后立即将前面所有必经点走掉。如果这个结论正确那状态是 \(nk\) 的，很容易转移。

然而需要注意这里向后走的费用是 \(2\)，于是类似：
\[ \begin{aligned} &ca \dots aaba\\ &01 \dots 1011 \end{aligned} \]
这样的数据可以卡掉。

但是我们可以考虑一个更平凡的结论：

• 考虑每次向后一段再向前，再向后一次，最终到达的那一个节点一定是第一次到达。

证明：例如：
\[ \begin{matrix} a & \to & \to & b &\to & c \\ & d & \leftarrow &\leftarrow &\leftarrow&\leftarrow \\ & & \to &\to &e \end{matrix} \]
我们显然可以改为：
\[ \begin{matrix} a & \to & \to & b & & c \\ & d & \leftarrow & && \\ & \to & \to &\to &e \\ & & & b+1 & \leftarrow \\ & & & \to& \to & c \end{matrix} \]
这样的话可以发现答案变小。

于是最终答案一定可以分为若干段，每一段从左边一直跳到右边，然后退回左边，并且两段之间无交。

于是我们考虑以下状态：
\(f(i,j)\) 表示当前在 \(i\)，已经从 \(j\) 走到 \(i\) 的答案。

\(g(i,j)\) 表示当前在 \(j\)，上一段的最右端是 \(i\) 的答案。

我们每次改变较小的还要改变的位置。

考虑转移有哪些：

第一种是 \(f(i,j) \to g(\text{next}(i),j)\) 即下一段第一个经过的是 \(j\) 。

第二种是 \(g(i,j) \to f(\text{first}(i+1,j),j)\) 即下一段退回到 \(i+1,j\) 这段的第一个必经点。

第三种是 \(g(i,j) \to f(\text{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;
}