Solution P6758 [BalticOI2013] Vim

说在前面

这是一道较为经典的线头动态规划题目。由于转移方程较为复杂且题解区图片较为简单，故写此篇带详细图片的题解。

题目思路

线头 dp 就是针对线段进行处理的 dp。

我们先对本题进行转化。
题目要求删去所有的 e，发现每删去一个 e 的代价为 $2$，即先从后一个字符移动到它，再删除。
我们先把所有的 e 删去，如果有 $cnt$ 个，最后额外付出的代价为 $2\times cnt$。

想要删去 e，新序列中的 e 的后一个字符必须被经过。
题目现在转化为在新序列上移动，要求某些点必须被经过，求移动的最小代价。

由于要向前走，一个点只会被经过奇数次，想要最优地移动，一个点只会被经过一或三次。

我们设计状态：

• $f_{i,a}$ 表示经过 $i$ 一次，且目标是字符 $a$ 的最小代价。
• $g_{i,a,b}$ 表示经过 $i$ 三次，且第一次目标是字符 $a$，第二次目标是字符 $b$ 的最小代价。

记 $need_i$ 表示这个点必须被经过。接下来是转移方程，直接丢张图：

第一种方法，直接不走 $i$，要求 $s_i\neq a\&\&!need_i$，因为移动只会到右边的第一个字符。

第二种，在 $i$ 处中转，注意一次操作代价为 $2$。

剩下两种，从 $g$ 转移，和上面同理：

对于 $g$，再丢一张图：

前两种方法，从 $f$ 转移，一种停留一种不停留，同时因为下方没走，所以需要花费额外代价：

另外四种其实也不难理解，就是上方跳或不跳，下方跳或不跳的组合方案：

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 70005, K = 10, INF = 0x3f3f3f3f;

int n, m = 0;
char base[N];
int s[N];
bool need[N];

int f[N][K], g[N][K][K];

int main() {
	scanf("%d %s", &n, base + 1);
	int ecnt = 0;
	bool flag = true;
	for (int i = 1; i <= n; i++) {
		if (base[i] == 'e') {
			ecnt++;
			flag = true;
		} else {
			s[++m] = base[i] - 'a' - ((base[i] < 'e') ? 0 : 1);
			need[m] = flag;
			flag = false;
		}
	}
	
	memset(f, INF, sizeof(f));
	memset(g, INF, sizeof(g));
	f[0][s[1]] = 0; // init
	int f1, g1;
	for (int i = 1; i <= m; i++) {
		for (int a = 0; a < K; a++) {
			f1 = INF;
			if (s[i] != a && !need[i]) f1 = min(f1, f[i - 1][a]);              //  flyU
			                           f1 = min(f1, f[i - 1][s[i]] + 2);       // jumpU
			if (s[i] != a)             f1 = min(f1, g[i - 1][s[i]][a]);        // stayU +  flyD
			                           f1 = min(f1, g[i - 1][s[i]][s[i]] + 2); // stayU + jumpD
			f[i][a] = f1;
			                           
			for (int b = 0; b < K; b++) {
				g1 = INF;
				if (s[i] != a)              g1 = min(g1, f[i - 1][a] + 3);          //  flyU +  flyD
				                            g1 = min(g1, f[i - 1][s[i]] + 5);       // jumpU +  flyD
				if (s[i] != a && s[i] != b) g1 = min(g1, g[i - 1][a][b] + 1);       //  flyU +  flyD + back
				if (s[i] != a)              g1 = min(g1, g[i - 1][a][s[i]] + 3);    //  flyU + jumpD + back
				if (s[i] != b)              g1 = min(g1, g[i - 1][s[i]][b] + 3);    // jumpU +  flyD + back
				                            g1 = min(g1, g[i - 1][s[i]][s[i]] + 5); // jumpU + jumpD + back
				g[i][a][b] = g1;
			}
		}
	}
	
	printf("%d", f[m][K - 1] + ecnt * 2 - 2);
	return 0;
}