CF 1728 D. Letter Picking 区间dp 1800

题意：一个长度为 n 并且 n 是偶数的非空字符串 s，Alice 有字符串 a，Bob有字符串 b，最初都是空的，从 Alice 开始轮流从 s 字符串的开头或者结尾取一个字符，移到自己的字符串的开头。最后谁的字符串大谁有赢，如果相等就平局。求对于每个字符串 s，游戏的结果是什么。

思路：区间 dp，dp[l][r] 表示从字符串 sl 到 sr-1 开始游戏最后的结果。-1表示Alice获胜，0表示平局，1表示Bob获胜。那么答案就是 dp[0][n]。因为每一轮取的字符要放在开头，所以后面轮次取的字母在更前面，所以当前这一轮的结果要从后一轮转移过来，从当前轮一人取一个字符有三种情况：开头和结尾一人取一个；两人都在开头取；两人都在结尾取；取完的结果分别是：dp[l + 1][r - 1] ; dp[l + 2][r] ; dp[l][r - 2]。对于 Bob 来说，Alice先手从一端选择一个字符后，Bob可以选择另一端，也可以选择同一端，也就是说Bob可以保证自己选到第一种情况。也可以选到第二种情况和第三种情况中的一种，而具体是哪一种是由 Alice 控制的。所以当前轮的结果应该是max(dp[l + 1][r - 1] , min(dp[l + 2][r], dp[l][r - 2]));但是要注意，三种情况中的平局，结果不一定是平局，要根据当前轮选择的字符来判断。

代码：

#include
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 2e5 + 10, P = 1e9 + 7, mod = 998244353;
int dp[2010][2010];
void solve() {
	string s;
	cin >> s;
	int n = s.size();
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++) dp[i][j] = 0;
	for(int len = 2; len <= n; len += 2) {
		for(int l = 0; l + len <= n; l++) {
			int r = l + len;
			int res = -1, res1 = -1, res2 = -1; 
			
			if(dp[l + 1][r - 1]) res = max(res, dp[l + 1][r - 1]);
			else if(s[l] == s[r - 1]) res = 0;
			
			if(dp[l + 2][r]) res1 = max(res1, dp[l + 2][r]);
			else {
				if(s[l] == s[l + 1]) res1 = 0;
				if(s[l] < s[l + 1]) res1 = 1;
			}
			
			if(dp[l][r - 2]) res2 = max(res2, dp[l][r - 2]);
			else {
				if(s[r - 1] == s[r - 2]) res2 = 0;
				if(s[r - 1] < s[r - 2]) res2 = 1;
			}
			dp[l][r] = max(res, min(res1, res2));
 		}
	}
	if(dp[0][n] == -1) cout << "Alice" << endl;
	else if(!dp[0][n]) cout << "Draw" << endl;
	else cout << "Bob" << endl;
}                
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int tt = 1;
	cin >> tt;
	while(tt--) {
		solve();
	}
	return 0;
}