P6758 [BalticOI2013] Vim

题目描述

给定一个长度为 $N$ 的字符串 $S$，Victor 的目标是将其中的 e 全部删除，而不删除其他字符。
Victor 使用 Vim 来解决这个问题。
然而，Victor 并不熟悉 Vim，他只知道这里面的三个指令：

• x：删除光标处的字符，光标位置不变，不可以在最后的字符处使用这个命令。
• h：将光标向左移动一格，如果光标位于第一个位置，则光标不动。
• f：其后接一个字符 $c$，其将会将光标移至其右边的第一个字符 $c$，$c\ne$e。
  请计算将其中的 e 全部删除，而不删除其他字符的最小按键数。

$\text{tips：}$一次$f$操作代价是$2$，一开始看成$1$得到了一些假结论，给$A$组口胡时锅了

Solution

不难想到一个暴力$dp$，设$f_{i,j}$表示前$i$个位置的$e$都已经被删了，当前光标跳到了位置$j$的最小代价，然后就可以做到$O(n^{2}v)$的复杂度，其中$v$为字符集大小
但是这不能接受，这时候就要引入一个叫做线头$dp$的东西
我们首先把字符中的$e$都给去掉，删掉一个$e$有两步操作，从后面那个字符移过来，删掉它，所以删掉一个$e$需要代价$2$
那么剩下的字符之间我们看作有一些边，如果有两个相邻字符之间原本是有$e$的，那这条边我们称之为
必经边，设$n{d}_i$表示$i-1,i$这条边是否是必经边

图是从这里嫖的LOJ2687 BalticOI2013 Vim 线头DP
这是我们移动时的大致形态，观察可以得出，一条边要么被一条从后面过来的$f$操作经过一次，要么被$f$操作一次，然后$h$回去，再$f$过去经过$3$次，必经边是必须被经过$3$次的
根据这个我们就可以设计出$dp$，设$f_{i,j}$表示$1\sim i+1$之间的边全部被经过，覆盖$i,i+1$一次的操作是$fj$的最小代价，$g_{i,j,k}$表示先覆盖$i,i+1$用了$fj$，$h$回来，然后又用了$fk$到了后面的最小代价
转移：
$$f_{i,j}=\min \{f_{i,j-1}(j\ne s_i\&!n{d}_i),f_{i-1,s_i}+2,g_{i-1,s_i,j}(j\ne s_i),g_{i-1,s_i,s_i}+2\}$$
$$g_{i,j,k}=\min \{f_{i-1,j}+3(j\ne s_i),f_{i-1,s_i}+5,g_{i-1,j,k}+1(j\ne s_i\&k\ne s_i),$$
$$g_{i-1,s_i,k}+3(k\ne s_i),g_{i-1,j,s_i}+3(j\ne s_i),g_{i-1,s_i,s_i}+5\}$$
然后就可以做到$O(n{v}^2)$了
一些细节：

• 1.$dp$中的答案没有包括$e$的代价最后要加上$2$
• 2.可以在字符串的最后加一个字符串中未出现的字符，删完$e$以后我们视作直接跳到了最后一个字符，方便统计答案

code

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+1000,V=10;
int n,m,nume,p[N+10],nd[N+10],f[N+10][V+1],g[N+10][V+1][V+1];char s[N+10];
int main()
{
    
	scanf("%d %s",&n,s+1);
	for(int i=1;i<=n;i++)
	{
    
		if(s[i]!='e') p[++m]=s[i]-'a',nd[m]=(s[i-1]=='e');
		else nume++;
	}
	for(int i=1;i<=m;i++)
		for(int j=0;j<=V;j++)
		{
    
			for(int k=0;k<=V;k++) g[i][j][k]=3*n+100;
			f[i][j]=3*n+100;
		}
	for(int i=0;i<=V;i++) if(i!='e'-'a') f[1][i]=2;
	for(int i=2;i<=m;i++)
		for(int j=0;j<=V;j++)
		{
    
			if(j!=p[i]&&!nd[i]) f[i][j]=min(f[i][j],f[i-1][j]);
			f[i][j]=min(f[i][j],f[i-1][p[i]]+2);
			if(j!=p[i]) f[i][j]=min(f[i][j],g[i-1][p[i]][j]);
			f[i][j]=min(f[i][j],g[i-1][p[i]][p[i]]+2);
			for(int k=0;k<=V;k++)
			{
    
				if(j!=p[i]) g[i][j][k]=min(g[i][j][k],f[i-1][j]+3);
				g[i][j][k]=min(g[i][j][k],f[i-1][p[i]]+5);
				if(j!=p[i]&&k!=p[i]) g[i][j][k]=min(g[i][j][k],g[i-1][j][k]+1);
				if(j!=p[i]) g[i][j][k]=min(g[i][j][k],g[i-1][j][p[i]]+3);
				if(k!=p[i]) g[i][j][k]=min(g[i][j][k],g[i-1][p[i]][k]+3);
				g[i][j][k]=min(g[i][j][k],g[i-1][p[i]][p[i]]+5);
			}
		}
	printf("%d",f[m][10]+2*nume-2);
	return 0;
}