P6758 [BalticOI2013] Vim 题解

· · 题解

转化

首先可以看出，那些 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} 的转移，分别表示：

\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} 的转移，分别表示：

知道这些就可以愉快地 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;
}