BOI2013 Vim

题目:

   Victor 正在使用 vim 编辑他的文章,他的文章只包含 abcdefghij 个字母,他想把他文章中所有的 e 都删除。Victor 并不是很熟悉 vim,它只懂得下面几个操作:
   x:删除光标所在的字母,光标位置不变。
   h:光标向左移。如果已经是行首就不会移。
   f:后面还会跟一个字母 c,表示跳到下一个字母 c 的位置。如果不存在那么就不会跳。
   悲剧的是 Victor 的键盘上 e 按键突然坏掉了……请问:Victor 最少需要按多少个键才能把所有的 e 删除。
   例如,如果当前的文本是 jeff[i]ehadabigidea,则
   x 操作后文本将变为 jeff[e]hadabigidea
   h 操作后文本将变为 jef[f]iehadabigidea
   fi 操作后文本将变为 jeffiehadab[i]gidea

思路:

   好神奇的线头dp.....
   为下文方便起见,只要光标从 一侧变到 另一侧,就叫经过。恰好落到 点上叫踩到。
   可以先把 e 从字符串中去掉,把每个 e 后面的标记成必经点,最终答案就是 e 的个数 走遍必经点的最小距离(因为可以在必经点上 hx 删掉 e)。
   写过 的暴力会发现,每一个被经过过的边被经过的次数一定是 。那么如果要从 ,一种情况是 之间的边只经过 次,另一种情况是恰好经过 次。
   为了方便统计价值,把每一次移动(hf)都从起点到终点画一条射线。统计答案时就统计每条射线的价值(这就是叫线头 dp 的原因?)
   设 表示 之间的边只经过 次,跳到下一个点字符是 个点引出的射线的最小代价 表示 之间的边经过 次,先跳到字符 ,然后回来一段再跳到字符 个点引出的射线的最小代价(参见图一图二)。
   每次从 时,要考虑的问题只有每种情况 会不会被踩到,从 引出的射线代价。
   转移 ,为了保证线不会一头栽到 上,必须满足 ,因为不会踩到 ,所以要求 不是必经点(见图三)。
   转移 的代价来自一次 f 操作(见图四)。
   转移 ,同样要求 的代价来自一次 h 操作(见图五)。
   转移 (见图六)。
   转移 ,要求 (见图七)。
   转移 ,要求 (见图八)。
   转移 ,要求 (见图九)。
   转移 (见图十)。
   转移 ,要求 (见图十一)。
   转移 ,(见图十二)。
   a _2_.jpg
   b _2_.jpg
   c _2_.jpg

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 7e4 + 5;

bool cur1;

char s[N];
bool mark[N];
int n;

int dp[N][15], g[N][15][15];

int main() {
    File(vim);
    scanf("%d", &n);
    int tot = 0, cnt = 0;
    bool flg = false;
    scanf("%s", s + 1);
    rep(i, 1, n) {
        if(s[i] != 'e') {
            s[++tot] = s[i] - 'a';
            mark[tot] = flg;
            flg = false;
        }
        else flg = true, cnt++;
    }
    n = tot;
    mset(dp, 63); mset(g, 63);
    dp[0][s[1]] = 0;
    rep(i, 1, n) {
        rep(j, 0, 10) {
            if(!mark[i] && s[i] != j) tomin(dp[i][j], dp[i - 1][j]);
            tomin(dp[i][j], dp[i - 1][s[i]] + 2);
            if(s[i] != j) tomin(dp[i][j], g[i - 1][s[i]][j] + 1);
            tomin(dp[i][j], g[i - 1][s[i]][s[i]] + 3);
            rep(k, 0, 10) {
                if(s[i] != k && s[i] != j) tomin(g[i][k][j], g[i - 1][k][j] + 1);
                if(s[i] != j) tomin(g[i][k][j], g[i - 1][s[i]][j] + 3);
                if(s[i] != k) tomin(g[i][k][j], g[i - 1][k][s[i]] + 3);
                tomin(g[i][k][j], g[i - 1][s[i]][s[i]] + 5);
                if(s[i] != k) tomin(g[i][k][j], dp[i - 1][k] + 2);
                tomin(g[i][k][j], dp[i - 1][s[i]] + 4);
            }
        }
    }
    printf("%d\n", dp[n][1] - 2 + cnt * 2);
    return 0;
}