Description
Input
第一行包含了整数N，表示该文档的长度。下一行包含N个字符，每一个都是十个小写字母“a”到“j”之一。输入的第一个和最后一个字母都不是“e”。
Output
输出一个整数，表示Victor需要删除所有的“e”最少的按键次数。
Sample Input
35
chefeddiefedjeffeachbigagedegghehad
Sample Output
36
解释：其中一个最优方案是：fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx
Data Constraint
50%数据：N ≤ 500
另外10%的数据：N ≤ 5000
100%的数据：N ≤ 70 000
题解
50%
考虑DP。
我们设状态(f_{[i,j]})表示当前第i个位置，把前j个e都给删去的最小步数。
怎么转移？
由于每个f操作都是往右跳，h是往左跳。
那么我们发现，每次从i往右跳到j后，一定是把i到j里面的所有e都删去后才继续往右跳，否则不优。
那么每次都是把某一段的e都给删掉。
于是就很好转移的，每次考虑枚举下一个e是什么，利用预处理求出代价后转移。
注意各种小细节。
时间复杂度：(O(n^3))
60%
我不费。（其实是我没打过）
似乎转移状态和上面的很相似，设(f_{[i,j]})表示当前第i个位置，1~j位置的所有e都去掉的最小步数。
我们发现，每次j是只可能往右走，而i往左跳或往右跳都是可以的。
那么我们固定一个k，分两种情况：
1、f操作。枚举一个新的字符，然后i往右跳。
2、h操作。我们如果k右边i左边有e没删，那么就把i往左边跳即可。
实际上转移好像比较猎奇。
但是时间是(O(n^2*10))的。
100%
这据说是一个叫线头DP的玩意儿，我从来没有听说过。
似乎DP比较神奇，理解起来也很容易。
（主要是题解很棒）
https://www.cnblogs.com/Itst/p/10339605.html、
https://www.cnblogs.com/cjyyb/p/11146822.html
看完你就懂了。比我写得详细多了。
其中有一个东东没有讲得特别清楚：
就是DP方程其实记录的是当前第i个位置以前的h操作和f操作。
所以说在看到q的转移的时候我们可以看到它没有求i+1到j这部分的答案。
这个地方注意，其他都很容易。
标程
uses math;
var
i,j,k,l,n,m,len,maxx,si:longint;
mip:array[1..70000] of boolean;
p:array[0..70000,1..11] of longint;
q:array[0..70000,1..11,1..11] of longint;
s,t:ansistring;
begin
//assign(input,'2data.in');reset(input);
readln(n);
readln(s);
for i:=1 to n do
begin
if s[i]='e' then
begin
inc(m);
end
else
begin
inc(len);
t:=t+s[i];
if (i>1) and (s[i-1]='e') then
begin
mip[len]:=true;
end;
end;
end;
inc(len);
t:=t+'k';
fillchar(p,sizeof(p),127 div 3);
fillchar(q,sizeof(q),127 div 3);
maxx:=p[0,1];
p[0,ord(t[1])-96]:=0;
q[0,ord(t[1])-96,ord(t[1])-96]:=0;
for i:=1 to len do
begin
si:=ord(t[i])-96;
for j:=1 to 11 do
begin
p[i,j]:=min(p[i-1,si]+2,q[i-1,si,si]+2);
if (j<>si) and (not mip[i]) then p[i,j]:=min(p[i,j],p[i-1,j]);
if (j<>si) then p[i,j]:=min(p[i,j],q[i-1,si,j]);
for k:=1 to 11 do
begin
q[i,j,k]:=min(p[i-1,si]+5,q[i-1,si,si]+5);
if (j<>si) then q[i,j,k]:=min(q[i,j,k],min(p[i-1,j]+3,q[i-1,j,si]+3));
if (k<>si) then q[i,j,k]:=min(q[i,j,k],q[i-1,si,k]+3);
if (j<>si) and (k<>si) then q[i,j,k]:=min(q[i,j,k],q[i-1,j,k]+1);
end;
end;
end;
writeln(m*2-2+p[len-1,11]);
end.