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