题目描述
给定长度NN的字符串SS，Victor 其中的目标是e全部删除，而不是其他字符。
Victor 使用Vim解决这个问题。
然而，Victor 并不熟悉Vim，他只知道三个指令：
x：删除光标处的字符，光标位置不变，最终字符处不能使用此命令。h：若光标位于第一位，则光标不动。f：然后连接一个字符cc，它将光标移到右边的第一个字符cc，c\not =c=e。
请计算其中的e删除所有其他字符而不是最小字符数。
输入格式
第一行为是整数NN。
接下来，一行一个字符串SS。
输出格式
只有一行整数表示其中e删除所有其他字符而不是最小字符数。
输入输出样例
复制
35 chefeddiefedjeffeachbigagedegghehad
复制
36
说明/提示
样例解释
fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx为最优解。
数据范围和限制
- 对于5050保证分数据N\le 500N≤500。
- 对于另外1010保证分数据N\le 5\times 10^3N≤5×103。
- 对于100\0%的数据，保证1\le N\le 7\times 10^41≤N≤7×104，S_i\in\{Si∈{
a\sim～j\}}，S_1,S_N\not=S1,SN=e。
说明
本题译自Baltic Olympiad in Informatics 2013Day 2T3 Vim。
上代码：
#include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int maxn=7e4,alpha='k'-'a' 1; int n,len,cnte,f[maxn 1][alpha],g[maxn 1][alpha][alpha]; bool key[maxn 2]; char s[maxn 3]; int main() { memset(f,0x3f,sizeof f); memset(g,0x3f,sizeof g); scanf("%d\n",&n); for(int i=1,check=0;i<=n; i) { char t=getchar(); if(t=='e') check= cnte; else { key[ len]=check; s[len]=t-'a'; check=0; } } f[0][s[1]]=0; for(int i=1;i<=len; i) for(int j=0;j<alpha; j) { if(j!=s[i]) { if(!key[i]) f[i][j]=f[i-1][j]; f[i][j]=min(f[i][j],g[i-1][s[i]][j]); } f[i][j]=min(f[i][j],min(f[i-1][s[i]],g[i-1][s[i]][s[i]]) 2); for(int k=0;k<alpha; k) { if(j!=s[i]&&k!=s[i]&&k!=s[i]) g[i][j][k]=g[i-1][j][k] 1; if(j!=s[i]) g[i][j][k]=min(g[i][j][k],min(f[i-1][j],g[i-1][j][s[i]]) 3); if(k!=s[i]) g[i][j][k]=min(g[i][j][k],g[i-1][s[i]][k] 3); g[i][j][k]=min(g[i][j][k],min(g[i-1][s[i]][s[i]] 5,f[i-1][s[i]] 5)); } } printf("%d",f[len][alpha-1] (cnte<<1)-2); return 0; }