题解：P6758 [BalticOI 2013] Vim

· · 题解

题意

给定一个长度为 n 的字符串 s，你需要通过下面几个操作把其中的字符 e 全部删掉。

求把字符串中所有的 e 全部删掉所需要的最小操作数。

思路

考虑到光标只能左移，所以考虑移到一段 e 的后一个字符，并称这个字符为关键点，则每个关键点都应该被经过至少一次，然后左移把这一段 e 全部删掉，发现左移的区间不会相交，稍微证明一下，如以下图：

一定不如以下操作：

通过调整法就能把相交的左移区间变成不相交，并且使操作数减小。（以上图仅供感性理解，并不太严谨）

如果我们在给定的字符串 s 后添加一个特殊字符，并令操作结束后一定停留在这个特殊字符上，发现在输出答案时减二就好了。

此时如果考虑朴素的 dp，一般只能是 O(n^2) 的复杂度，没办法直接计算，但是根据以上信息就能发现，在一个字符上只能有两种可能，经过两条跳跃和一条左移的线段或者一条跳跃的线段。即以下两种情况：

所以这样就可以给出两个 dp 的式子了，一个 f_{i,x} 表示计算到第 i 个字符段，跳的目标点为 x 的最小操作数，和一个 g_{i,x,y} 表示计算到第 i 个，且这一段线头向右移动到 x，并再向左后第二次向右移动到 y 所需要的最小次数。

先考虑从 f 转移到 f，看下面两个图：

第一个 f_{i,x} 直接从 f_{i-1,x} 转移过来，即 f_{i,x}=f_{i-1,x}，保证 s_i\ne x，第二个 f_{i,x}=f_{i-1,s_i}+2，没有限制，其实就是考虑线头是否在这个片段中，进行一些分类即可。

接下来就是从 g 转移到 f 了，接着看图：

因为是从 g 转移过来的，所以第二维一定为 s_i，所以第一个转移就是 f_{i,x}=g_{i-1,s_i,x}，保证 x\ne s_i，而第二个转移就是 f_{i,x}=g_{i-1,s_i,s_i}+2，没有限制。

继续向后边走，考虑 f 向 g 的转移，不废话，继续上图，

第一个是从 f 转移到 g，所以 g_{i,x,y}=f_{i-1,x}+3，而第二个 g_{i,x,y}=f_{i-1,s_i}+5。直接看着图片就可以写出转移式了，比较简单。

最后就是 g 转移到 g 了，这个会困难一点，但也没什么区别，画出图来也就是简单的了。

第一个 g_{i,x,y}=g_{i-1,x,y}+1，需要保证 x\ne s_i,y\ne s_i，第二个 g_{i,x,y}=g_{i-1,s_i,y}+3 保证 y\ne s_i，第三个 g_{i,x,y}=g_{i-1,x,s_i}+3 保证 x\ne s_i，最后一个就是 g_{i,x,y}=g_{i-1,s_i,s_i}+5，没有限制，这样四种转移都统计完了，其他就是一些小问题，直接就看代码吧。

#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define int long long
#define ld long double
#define ull unsigned long long
// #define ll long long
#define LL __int128
// #define faster 1
#define pii pair<int,int>
#define piv pair<int,vi>
#define pic pair<int,char>
#define pdi pair<double,int>
#define mst(x,y) memset(x,y,sizeof x)
#define D(x) cout<<#x<<": "<<x<<endl;
#define DE(x) cout<<#x<<": "<<x<<" ";
#define MAXSIZE 1<<21
#define pl p<<1
#define pr p<<1|1
using namespace std;
constexpr int ksm(int x,int a,int mod){int mul=1;while(a){if(a&1)mul=1ll*mul*x%mod;x=1ll*x*x%mod;a>>=1;}return mul;}
// inline int ksm(int x,int a,int mod){int mul=1;while(a){if(a&1)mul=1ll*mul*x%mod;x=1ll*x*x%mod;a>>=1;}return mul;}
namespace lry{
    char buf[MAXSIZE],*p1=buf,*p2=buf;
    char pbuf[MAXSIZE],*pp=pbuf;
    inline int gc(){
        #if faster
            return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
        #else
            return getchar();
        #endif
    }
    inline void pc(const char &c){
        #if faster
            if(pp-pbuf==MAXSIZE) fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;*pp++=c;
        #else
            putchar(c);
        #endif
    }
    inline bool blank(const char x){return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
    inline void read(double &rdx){double t=0;int x=0,s=0,f=1;char c;do c=gc();while(!isdigit(c)&&c!='-'&&c!='.');if (c=='-')f=-1,c=gc();while(isdigit(c)&&c!='.')x=(c^48)+(x<<1)+(x<<3),c=gc();if(c=='.')c=gc();else{rdx=x*f;return;}while(c>='0'&&c<='9')t=t*10+(c^48),s=-~s,c=gc();while(s--)t/=10;rdx=(x+t)*f;}
    inline void read(string &x){x="";char a=gc();for(;blank(a)&&(a^-1);a=gc());for(;!blank(a)&&(a^-1);a=gc())x+=a;}
    inline void read(char &x){char a=gc();for(;blank(a)&&(a^-1);a=gc());if(!blank(a)&&(a^-1))x=a;}
    inline void read(int &x){int ret=0,f=0;char ch=gc();while(!isdigit(ch)){if(ch=='-')f=1;ch=gc();}while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+(ch^48);ch=gc();}x=(f?-ret:ret);}
    inline void read(ull &x){ull ret=0;char ch=gc();while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+(ch^48);ch=gc();}x=ret;}
    // inline void read(ll &x){ll ret=0,f=0;char ch=gc();while(!isdigit(ch)){if(ch=='-')f=1;ch=gc();}while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+(ch^48);ch=gc();}x=(f?-ret:ret);}
    inline void read(LL &x){LL ret=0,f=0;char ch=gc();while(!isdigit(ch)){if(ch=='-')f=1;ch=gc();}while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+(ch^48);ch=gc();}x=(f?-ret:ret);}
    template<typename t,typename ...T> inline void read(t &x,T&...y){read(x),read(y...);}
    inline void write(int x){if(x<0)pc('-'),x=-x;if(x>9)write(x/10);pc(x%10+48);}
    inline void write(char x){pc(x);}
    inline void write(ull x){if(x>9)write(x/10);pc(x%10+48);}
    // inline void write(ll x){if(x<0)pc('-'),x=-x;if(x>9)write(x/10);pc(x%10+48);}
    inline void write(LL x){if(x<0)pc('-'),x=-x;if(x>9)write(x/10);pc(x%10+48);}
    inline void write(const char *x){fputs(x,stdout);}
    inline void write(const string &x){fputs(x.c_str(),stdout);}
    inline void writeln(int x){write(x),pc('\n');}
    inline void writetr(int x){write(x),pc(' ');}
    inline void writeln(char x){write(x),pc('\n');}
    inline void writetr(char x){write(x),pc(' ');}
    inline void writeln(ull x){write(x),pc('\n');}
    inline void writetr(ull x){write(x),pc(' ');}
    // inline void writeln(ll x){write(x),pc('\n');}
    // inline void writetr(ll x){write(x),pc(' ');}
    inline void writeln(LL x){write(x),pc('\n');}
    inline void writetr(LL x){write(x),pc(' ');}
    inline void writeln(string x){write(x),pc('\n');}
    inline void writetr(string x){write(x),pc(' ');}
    template<typename t,typename ...T> inline void write(t x,T...y){write(x),write(y...);}
}
using namespace lry;
constexpr int N=70000+10,M=10+10,QMAX=1000000+10,inf=0x3f3f3f3f3f3f3f3f,base=133,mod=1000000007;
constexpr int base1=233,base2=133,mod1=998244353,mod2=1000000087;
constexpr int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
constexpr int into[4]={2,3,0,1};
constexpr double alpha=0.75,eps=1e-9;
int n,cnt,a[N],t[N],f[N][M],g[N][M][M];
string s;
signed main(){
    read(n,s); s=" "+s;
    int _n=0;
    bool flag=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='e') cnt++,flag=1;
        else t[++_n]=s[i]-'a',a[_n]=flag,flag=0;
    }
    n=_n;
    memset(f,0x3f,sizeof f);
    memset(g,0x3f,sizeof g);
    f[0][t[1]]=0;
    for(int i=1;i<=n;i++){
        for(int x=0;x<11;x++){
            if(!a[i]&&x!=t[i]) f[i][x]=min(f[i][x],f[i-1][x]);
            f[i][x]=min(f[i][x],f[i-1][t[i]]+2);
        }
        for(int x=0;x<11;x++){
            if(x!=t[i]) f[i][x]=min(f[i][x],g[i-1][t[i]][x]);
            f[i][x]=min(f[i][x],g[i-1][t[i]][t[i]]+2);
        }
        for(int x=0;x<11;x++){
            for(int y=0;y<11;y++){
                if(x!=t[i]) g[i][x][y]=min(g[i][x][y],f[i-1][x]+3);
                g[i][x][y]=min(g[i][x][y],f[i-1][t[i]]+5);
            }
        }
        for(int x=0;x<11;x++){
            for(int y=0;y<11;y++){
                if(x!=t[i]&&y!=t[i]) g[i][x][y]=min(g[i][x][y],g[i-1][x][y]+1);
                if(y!=t[i]) g[i][x][y]=min(g[i][x][y],g[i-1][t[i]][y]+3);
                if(x!=t[i]) g[i][x][y]=min(g[i][x][y],g[i-1][x][t[i]]+3);
                g[i][x][y]=min(g[i][x][y],g[i-1][t[i]][t[i]]+5);
            }
        }
    }
    writeln(f[n][10]-2+cnt*2);
    #if faster
        fwrite(pbuf,1,pp-pbuf,stdout);
        pp=pbuf;
    #endif
    return 0;
}
/*

*/