P6758 [BalticOI2013] Vim

Title Description

Given a length of $N$ String $S$,Victor The goal is to make e Delete all , Without deleting other characters .
Victor Use Vim To solve this problem .
However ,Victor Not familiar with Vim, He only knows the three instructions ：

• x： Delete the character at the cursor , The cursor position does not change , You cannot use this command at the last character .
• h： Move the cursor one space to the left , If the cursor is in the first position , The cursor does not move .
• f： Followed by a character $c$, It will move the cursor to the first character to its right $c$,$c\ne$e.
  Please calculate the e Delete all , Without deleting other characters Key Count .

$\text{tips：}$ once $f$ The operational cost is $2$, At first it was seen as $1$ Got some false conclusions , to $A$ Set up a Hushi pot

Solution

It's not hard to think of a violent $dp$, set up $f_{i,j}$ Before presentation $i$ Location $e$ Have been deleted , The current cursor jumps to the position $j$ The minimum cost of , Then you can do $O(n^{2}v)$ Complexity , among $v$ Is the character set size
But this is unacceptable , At this time, a thread head is introduced $dp$ Things that are
Let's start with the characters $e$ Get rid of , Delete one $e$ There are two steps , Move from the last character , Delete it , So delete one $e$ It takes a price $2$
So the rest of the characters have some edges , If there were two adjacent characters, there would have been $e$ Of , This side we call
You have to go through the side , set up $n{d}_i$ Express $i-1,i$ Whether this edge is a required edge

The picture is about whoring from here LOJ2687 BalticOI2013 Vim Thread head DP
This is the general shape when we move , It can be observed that , One side is either by one coming from the back $f$ The operation goes through once , Or be $f$ Operating a , then $h$ Go back , Again $f$ In the past $3$ Time , Must pass edge is must be passed $3$ Time of
According to this, we can design $dp$, set up $f_{i,j}$ Express $1\sim i+1$ All the edges between are passed through , Cover $i,i+1$ One operation is $fj$ The minimum cost of ,$g_{i,j,k}$ Indicates to overwrite first $i,i+1$ It was used $fj$,$h$ Come back , And then again $fk$ To the minimum cost behind
Transfer ：
$$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\}$$
Then you can do $O(n{v}^2)$ 了
Some details ：

• 1.$dp$ The answer in does not include $e$ At the end of the day $2$
• 2. You can add a character that does not appear in the string to the end of the string , End of deletion $e$ In the future, we regard it as jumping directly to the last character , It is convenient to count the answers

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;
}