D. Letter Picking (博弈/区间dp)

题目
参考

题意

给定一个长度为偶数的字符串s，Alice和Bob轮流操作该字符串，Alice先走。初始时Alice和Bob各自有一个空字符串。

对于每次操作，从字符串中s，选择第一个元素，或者最后一个元素，移除，并添加到自己的字符串的头部。

一直都s字符串为空串，则结束该过程

最终，Alice和Bob的字符串中，字典序最小的，即为胜者。
问，如果Alice和Bob都采取明智的策略，谁最终会是胜者。如果平局，则输出Draw

思路

因为是添加到队头，所以影响胜利的关键，是最里边的元素。
定义dp[l][r]表示操作[l,r]的子区间的胜利者，-1表示Alice，0表示平局，1表示Bob。有两种选择。

• 选择l上的字符，那么此时对手可以操作区间[l+1,r]，此时对手可以选择l+1或者r上的字符，对手会选择对他有利的局面。
• 选择r上的字符串，那么此时对手可以操作区间[l,r-1]，此时对手可以选择l或者r-1上的字符，对手会选择对他有利的局面。

对于当前区间[l,r]，假设我方选择l，对方选择了r。

• 如果dp[l-1][r-1]不为0，说明区间[l-1,r-1]已经抉择出胜利者了，l和r位置上字符谁大都不影响局面了。
• 如果dp[l-1][r-1]为0，说明区间[l,r]是平局状态，此时就要看l和r位置上字符的大小

其他场景，类似分析。详见代码

代码

#include 
using namespace std;
const int maxn = 2010;
//#define debug

int n;
char s[maxn];
int dp[maxn][maxn];
int cmp(char a, char b) {
	if (a == b) {
		return 0;
	}
	return a < b ? -1 : 1;
}
void solve() {
	scanf("%s", s + 1);
	n = strlen(s+1);
	// init
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			dp[i][j] = 0;
		}
	}
	for (int i = 1; i + 1 <= n; ++i) {
		if (s[i] != s[i+1]) {
			dp[i][i+1] = -1;
		}
		
	}
	for (int len = 2; len <= n; len += 2) {
		for (int l = 1; l + len + 1 <= n; ++l) {
			int r = l + len + 1;
			dp[l][r] = 1;
			int res; // res表示Bob能选择的最有利（最接近1）的局面 
#define CMP_LR(a, b) {\
	res = -1; \
	if (dp[l+1][r-1] != 0) { \
		res = max(res, dp[l+1][r-1]); \
	} else { \
		res = max(res, cmp(s[a], s[b])); \
	} \
}
			// choose l
			CMP_LR(l, r)
			if (dp[l+2][r] != 0) {
				res = max(res, dp[l+2][r]);
			} else {
				res = max(res, cmp(s[l], s[l+1]));
			}
			dp[l][r] = res;
			
			
			// choose r
			CMP_LR(r, l)
			if (dp[l][r-2] != 0) {
				res = max(res, dp[l][r-2]);
			} else {
				res = max(res, cmp(s[r], s[r-1]));
			}
			dp[l][r] = min(dp[l][r], res);// dp[l][r]是Alice最有利（最接近-1）的局面 
		}
	}
	if (dp[1][n] == 0) {
		printf("Draw\n");
	} else {
		printf("%s\n", dp[1][n] == -1 ? "Alice" : "Bob");
	}
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

GZH

对方正在debug