「BalticOI 2013」Vim

题目描述

Victor 正在使用 vim 编辑他的文章，他的文章只包含 abcdefghij 这 1010 个字母，他想把他文章中所有的 e 都删除。Victor 并不是很熟悉 vim，它只懂得下面几个操作：

• x：删除光标所在的字母，光标位置不变。
• h：光标向左移。如果已经是行首就不会移。
• f：后面还会跟一个字母 c，表示跳到下一个字母 c 的位置。如果不存在那么就不会跳。

悲剧的是 Victor 的键盘上 e 按键突然坏掉了……请问：Victor 最少需要按多少个键才能把所有的 e 删除。

例如，如果当前的文本是 jeff[i]ehadabigidea，则

• x 操作后文本将变为 jeff[e]hadabigidea
• h 操作后文本将变为 jef[f]iehadabigidea
• fi 操作后文本将变为 jeffiehadab[i]gidea

思路

神仙(DP)题。

首先，我们发现，字符串可以看成由若干个(e)段与非(e)段组成，每个(e)段都必定通过(h)和(x)操作完成，那么，每个非(e)段的开头必定经过（第一个除外）。这样一波分析后，有这样的小结论：
把删除，跳e的操作数预处理出来。接下来就只用把非e段接起来，求跳它所需的最小步数（有一些点必须跳到）。

预处理的操作数其实就是(cnt_e*2).

接下来就是搞定非(e)段的事了，由人类智慧可知，跳法大致长成这样：

https://boi2013.informatik-olympiade.de/wp-content/uploads/2013/05/vim-spoiler.pdf
（全英文。。。）不过感性想想，也挺显然。

接下来，看图，注意到什么了吗，每个点要么被经过一次，要么被经过三次。那么就可以开始想dp式子了。怎样才能正确涵盖所有状态。。

定义：
[ f[i][j]为最后通过f_j经过i位置的最少步数 ]
[ dp[i][j][k]为最后通过f_j,f_k以及一次h经过i位置3次的最小步数 ]
接下来就是漫长而恶心的转移了，为了方便理解，每个转移都大致解释一下吧！

f的转移

//head[i]为i是否为必经的点
int &h=f[i][j];
int p=txt[i-1];//上一个位置的字母-'a'
h=min(h,f[i-1][p]+2);
//表示上次刚好跳到它后面，再跳一次经过i
h=min(h,dp[i-1][p][p]+2);
//和上一个一样，就是上个位置经过三次，再跳一次经过i
if(!head[i-1]&&p!=j)h=min(h,f[i-1][j]);
//首先p!=j，表示上一次跳过了i-1，即没有停在i-1上，不过这样的前提是i-1不是必经的点。这样必经i
if(p!=j)h=min(h,dp[i-1][p][j]);
//同上，上一个点经过了三次

dp的转移

int p=txt[i-1];
int &h2=dp[i][j][k];
h2=min(h2,f[i-1][p]+5);
//停在i-1上，两次f加一次h（5步），经过i三次
h2=min(h2,dp[i-1][p][p]+5);
//经过i-1三次，停在i-1上，也是5步经过i三次
if(p!=j){
    h2=min(h2,f[i-1][j]+3);
    //跳过i-1，至少到达i.于是只需一次h和f(3步)
    h2=min(h2,dp[i-1][j][p]+3);
    //经过i-1三次，第一次跳过i-1，3步
}
if(p!=k)h2=min(h2,dp[i-1][p][k]+3);
//经过i-1三次，第三次跳过i-1,3步
if(p!=j&&p!=k)h2=min(h2,dp[i-1][j][k]+1);
//两次都跳过i-1,只需h一次

就这样转移就差不多了，还有一个小细节，在原数组中找答案比较蛋疼。那么还有一个小技巧，在字串最后再加一个‘a‘+10，那么只要拿(f[len][10]-2)再加上删跳e的步数即可（跳到‘a‘+10多用了两步）。

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define FOR(i,l,r) for(register int i=(l),i##R=(r);i<=i##R;i++)
#define DOR(i,r,l) for(register int i=(r),i##L=(l);i>=i##L;i--)
#define loop(i,n) for(register int i=0,i##R=(n);i<i##R;i++)
using namespace std;
typedef long long ll;
template<typename A,typename B>inline void chkmax(A &x,const B y){if(x<y)x=y;}
template<typename A,typename B>inline void chkmin(A &x,const B y){if(x>y)x=y;}
const int inf=1e9;
const ll INF=1e18;
const int N=7e4+5,M=11;
int n,len;
char str[N];int txt[N];
bool head[N];//是否必经（非e段的开头） 
int f[N][M];//从i位置的左边，通过fj操作，穿过或停在i上的最少步数 
int dp[N][M][M];//从i位置的左边，依次通过fj,h,fk,经过i三次的最少步数 
int main(){
    freopen("vim.in","r",stdin);
    freopen("vim.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",str+1);
    int cost=0;bool p=0;
    FOR(i,1,n){//接非e段，预处理删跳e的步数，找出必经点
        if(str[i]=='e'){
            cost+=2;
            p=1;
        }
        else {
            len++;
            head[len]=p;p=0;
            str[len]=str[i];txt[len]=str[i]-'a';
        }
    }
    len++;
    FOR(i,10){
        f[1][i]=inf;
        FOR(j,10)dp[1][i][j]=inf;
    }
    f[1][txt[1]]=0;
    FOR(i,2,len){
        FOR(j,10){
            f[i][j]=inf;
            int &h=f[i][j];
            int p=txt[i-1];
            chkmin(h,f[i-1][p]+2);
            chkmin(h,dp[i-1][p][p]+2);
            if(!head[i-1]&&p!=j)chkmin(h,f[i-1][j]);
            if(p!=j)chkmin(h,dp[i-1][p][j]);
            FOR(k,10){
                dp[i][j][k]=inf;
                int &h2=dp[i][j][k];
                chkmin(h2,f[i-1][p]+5);
                chkmin(h2,dp[i-1][p][p]+5);
                if(p!=j){
                    chkmin(h2,f[i-1][j]+3);
                    chkmin(h2,dp[i-1][j][p]+3);
                }
                if(p!=k)chkmin(h2,dp[i-1][p][k]+3);
                if(p!=j&&p!=k)chkmin(h2,dp[i-1][j][k]+1);
            }
        }
    }
    printf("%dn",f[len][10]+cost-2);
    return 0;
}