P13407 [GCJ 2010 Finals] Letter Stamper 题解

这篇题解有点魔怔。

本题应该有很多不同的 DP 方法，但是核心应该都大同小异。

观察栈中元素的性质，发现显然没有两个距离为一的相同的元素，若有则一定更劣。

再想想，发现显然没有两个距离为二的相同的元素，若有则一定不优。

再想想，发现栈中相邻的三个元素一定互不相同（即相邻的三个元素一定是 ABC 的一个排列）。

再想想，假设我们知道当前栈的大小、栈顶元素与栈顶元素的下一个元素（若有），我们就可以推出整个栈的情况。

再想想，如果我们刚刚打印完 ，那么栈顶元素一定就是 。

再想想，如果我们要打印一个非栈顶元素 ，可以选择反复弹出栈顶元素或者反复加入新元素，直到栈顶是 。

于是你想到了 DP。设栈顶的前三个元素是 。设 表示刚刚打印了 ，当前栈的大小是 且 的最小操作次数。有了 ，自然可以推出 。

转移是显然的，根据 分类讨论即可。唯一的细节是 的情况，此时会多一种转移，即先把栈清空，再向栈中加入 。另外，当 时，此时没有 ，但是 的取值会影响栈的情况，从而影响后续的 DP。设 ABC 中除 的两个元素分别是 和 ，那么 与 应该互相取 。

时间复杂度 ，不至于有很大的常数。

提交记录

#include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i <= e; ++i)
using namespace std;

int n, a[7005], dp[2][7005][3], ans;
char s[7005];

int solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	rep(i, 1, n) {
		a[i] = s[i] - 'A';
	}
	rep(i, 0, 1) {
		rep(j, 1, n + 2) {
			rep(y, 0, 2) {
				dp[i][j][y] = 0x3f3f3f3f;
			}
		}
	}
	ans = 0;
	rep(i, 1, n) {
		rep(j, 1, i) {
			rep(y, 0, 2) {
				dp[i & 1][j][y] = 0x3f3f3f3f;
				int x = a[i], &f = dp[i & 1][j][y];
				if(x == y) {
					continue;
				}
				int z = 3 - x - y;
				if(a[i - 1] == x) {
					f = min(f, dp[(i & 1) ^ 1][j][y] + 1);
				} else if(a[i - 1] == y) {
					if(j > 1) f = min(f, dp[(i & 1) ^ 1][j - 1][z] + 2);
					f = min(f, dp[(i & 1) ^ 1][j + 2][z] + 3);
				} else if(a[i - 1] == z) {
					f = min(f, dp[(i & 1) ^ 1][j + 1][x] + 2);
					if(j > 2) f = min(f, dp[(i & 1) ^ 1][j - 2][x] + 3);
				}
			}
		}
		int x = a[i], y = not a[i], z = 3 - x - y;
		dp[i & 1][1][y] = dp[i & 1][1][z] = min({dp[i & 1][1][y], dp[i & 1][1][z], ans + 2});
		ans = 0x3f3f3f3f;
		rep(j, 1, i) {
			rep(y, 0, 2) {
				ans = min(ans, dp[i & 1][j][y] + j);
			}
		}
	}
	return ans;
}

int main() {
	int T = 1; scanf("%d", &T);
	rep(i, 1, T) {
		printf("Case #%d: %d\n", i, solve());
	}
	return 0;
}