题解 [SCOI2007]压缩

好题。

显然区间 dp，令 \(f_{l, r}\) 为 \([l, r]\) 之间的最短的长度。如果我们要压缩，那么就要考虑 M 与 R 的位置。由于我们大体是从左往右来转移的，所以显然我们只需要记录一下 M，R 是可以枚举的。令 \(f_{l, r, 0/1}\) 代表 \([l, r]\) 之间有没有 M 的最短长度。

我们默认 \((l - 1)\) 的位置上有一个 M。首先我们考虑放 R。显然我们可以只在 \(r + 1\) 的位置上放 R，我们判断一下 \([l, r]\) 区间左右两端是不是一样的，如果是，则有 \(f_{l, r, 0} = \min\{f_{l, mid, 0} + 1, f_{l, r, 0}\}\)。为什么不是 \(f_{mid + 1, r, 0} + 1\)？因为这个位置没有做到。

然后我们考虑平常的操作。对于 \(f_{l, r, 0}\)，枚举 \(k\) 显然是 \(f_{l, r, 0} = \min\{f_{l, r, 0}, f_{l, k, 0} + r - k\}\)。\(f_{l, r, 1}\) 就枚举 \(k\) 作为加入 M 的地方，那么就是 \(f_{l, r, 1} = \min\{f_{l, r, 1}, \min\{f_{l, k, 0}, f_{l, k, 1}\} +\min\{f_{k + 1, r, 0}, f_{k + 1, r, 1}\} + 1\}\)。

然后就酱紫，就没了。

所以你会发现这题其实一点也不难，区间 dp 很一眼，状态也不难想，转移也很符合人类的逻辑。。。

em？em。。。

所以为什么 SX 在模拟赛没有想出来，，，？？？？？？？？？？？？？

SXSB

//SIXIANG

#include <iostream>

#include <cstring>

#define MAXN 1000

#define QWQ cout << "QWQ" << endl;

using namespace std;

string str;

bool check(int l, int r) {

	int len = (r - l + 1);

	if(len & 1) return 0;

	int mid = (r + l) / 2;

	for(int p = l; p <= (r + l) / 2; p++)

		if(str[p] != str[++mid])

			return 0;

	return 1;

}

int f[MAXN + 10][MAXN + 10][2];

int main() {

	memset(f, 0x3f, sizeof(f));

	int n; cin >> str;

	n = str.size();

	str = "$" + str;//CCF loves Monny $_$

	for(int p = 1; p <= n; p++)

		for(int i = p; i <= n; i++)

			f[p][i][0] = f[p][i][1] = i - p + 1;

	for(int len = 1; len <= n; len++) {

		for(int l = 1; l + len - 1 <= n; l++) {

			int r = l + len - 1;

			if(check(l, r)) f[l][r][0] = min(f[l][r][0], 1 + f[l][(r + l) / 2][0]);

			for(int k = l; k < r; k++) f[l][r][0] = min(f[l][r][0], f[l][k][0] + r - k);

			for(int k = l; k < r; k++)

				f[l][r][1] = min(f[l][r][1], min(f[l][k][0], f[l][k][1]) + min(f[k + 1][r][0], f[k + 1][r][1]) + 1);

		}

	}

	cout << min(f[1][n][0], f[1][n][1]) << endl;

}

话说这个我交到 darkbzoj 上炸了诶 qaq。

巴特西

题解 [SCOI2007]压缩

最新文章

热门文章