CF - D. Letter Picking（博弈 + 区间dp）

https://codeforces.com/problemset/problem/1728/D

题意
给定长度为 n 的字符串 S，n 为偶数。Alice 和 Bob 初始分别都有一个空串。
现在 Alice 和 Bob 要轮流操作，Alice 先手：

• 删掉串 S 的串首或者串尾元素，然后加到自己串的串首。
• 重复上述操作，直到串 S 为空。

最后串字典序小那个人获胜，如果两串相等，则平局。

问，在两人都尽可能想赢并且不想输的情况下（能赢就赢，否则就争取平局），最后的结果是什么？

思路
因为最后比较的是字典序，所以最后剩下的两个字符非常重要。因为是 Alice 先手，所以对于剩下的两个，Alice 先挑，肯定挑较小的那个，除非两个相同。所以最终的结果只有两种，要么 Alice 赢，要么平局。

然后就没有思路了。。

题解给的做法是这样的：
对于一个大区间是否是平局，可以由小区间来判断。
即，对于一个大区间来说，如果不管 Alice 拿左右端点的哪个，Bob 拿过剩下区间左右端一个和其相同的字符之后，剩下的区间是平局，那么大区间就是平局。

形式化讲，对于大区间 [l, r] 来说，有四种情况：

1. Alice 拿左端 a[l] 时，Bob 能拿剩下区间的左端 a[l+1] 并且 剩下区间 [l+2, r] 为平局；
2. Alice 拿左端 a[l] 时，Bob 能拿下剩下区间的右端 a[r] 并且 剩下区间 [l+1, r-1] 为平局；
3. Alice 拿右端 a[r] 时，Bob 能拿剩下区间的右端 a[r-1] 并且 剩下区间 [l, r-2] 为平局；
4. Alice 拿右端 a[r] 时，Bob 能拿下剩下区间的左端 a[l] 并且 剩下区间 [l+1, r-1] 为平局；

当 1, 2 情况出现至少一种，3, 4 情况出现至少一种时，就说明 Bob 能对 Alice 产生制约，这段大区间就能是平局。

而如果用区间dp先将小区间维护出来的话，大区间就能用小区间来更新，从而确定整个字符串是不是平局。

定义 f[i, j] 表示，区间 [l, r] 最后的结果是否是平局。

初始化的时候，看长度为 2 的区间，如果是两个相同的字符，那么就是平局，赋值为 1；否则为 0。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 2010, mod = 1e9+7;
int T, n, m;
char a[N];
int f[N][N];

bool check(int l, int r)
{
	int pdL = 0, pdR = 0;
	if(a[l] == a[l + 1] && f[l+2][r] || a[l] == a[r] && f[l + 1][r - 1]) pdL = 1;
	if(a[r] == a[r - 1] && f[l][r-2] || a[l] == a[r] && f[l + 1][r - 1]) pdR = 1;
	if(pdL && pdR) return 1;
	return 0;
}

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> a + 1;
		n = strlen(a + 1);
		
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				f[i][j] = 0;
		
		for(int i=1;i<n;i++)
			if(a[i] == a[i + 1]) f[i][i + 1] = 1;
		
		for(int len = 4; len <= n; len += 2)
		{
			for(int i=1;i<=n;i++)
			{
				int j = i + len - 1;
				if(check(i, j)) f[i][j] = 1;
			}
		}
		if(f[1][n]) cout << "Draw\n";
		else cout << "Alice\n";
	}
	
	return 0;
}

经验
还是找必胜态或者必败态，在这道题中，不管你 Alice 操作哪一端，我 Bob 都有方式让剩下的区间是平局，那么这个大区间就是平局，这就是必胜态。

然后就是需要借助区间dp先把小区间的结果处理出来，大区间借助小区间的结果来判断。

很妙！