CF-Letter Picking(区间dp+博弈论)

D

题意：
给你一个长度2000的字符串。然后每个人轮流每次从字符串的头或者尾取一个字符，然后添加到自己的字符串的前面。如果字符拿完了就停止，如果谁的字符字典序小谁赢，输出谁赢，或者平局。

思考：

1. 当时看到这题就感觉没什么想法，然后贪心的话根本没法贪心。但是我看到数据2000，应该是一个n²的做法，可能是区间dp？因为做过许多区间dp只枚举两次，转移的时候只从区间的左右两端转移。 想了想但是还是没感觉，虽然想到了区间dp，但是还不知道怎么下手。而且也没去翻翻之前做过的dp，害，玛德真菜。
2. 其实这就是区间dp和倒推博弈的组合。牛客月赛40-跳跳跳跳跳，牛客多校-Z-Game on grid。所谓倒退dp就是先把可以确定的状态给确定好，那些不确定的状态从可以确定的状态来转移就行了。然后区间dp也是初始化那些最简单的情况也就是字符串长度为2的时候，如果两个字符不相同肯定是小A赢，否则初始化为平局。
3. 那么就是先枚举len，然后对于区间[i,j]。现在所有长度小于len的dp都处理好了。那么对于i，j判断小A和小B怎么选就ok了。不过要注意的是，如果比[i,j]小的区间有了小A赢或者小B赢的状态，那么i和j只能顺从这种状态，因为区间越小代表东西好多东西已经选过了，前面的字符串大小比后面的更有话语权。
4. 那么就对小A枚举2种情况，当A选i的时候，A是否可以必赢，当A选j的时候，A是否可以必赢。同理看B，当A选i的时候，B是否可以必赢，当A选j的时候，看B是否可以必赢。如果A有一个可以必赢，那么A就可以必赢。如果B有两个必赢B才能赢，因为A先选，不论A怎么选，我都赢才行。当然也可以判是否平局，但是平局不是太好判断，一般都是谁赢更好判断。

代码：

 #include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
char s[N];
int dp[M][M];

void solve()
{
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++) dp[i][j] = 0;
	}
	for(int i=1;i<n;i++)
	{
		if(s[i]!=s[i+1]) dp[i][i+1] = 1;
	}
	for(int len=3;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j = i+len-1;
			int suc1 = 0,suc2 = 0,res = 0;
			res = 0;
			if((dp[i+1][j-1]==0&&s[i]<s[j])||dp[i+1][j-1]==1) res++;
			if((dp[i+2][j]==0&&s[i]<s[i+1])||dp[i+2][j]==1) res++;
			if(res>=2) suc1 = 1;
			res = 0;
			if((dp[i+1][j-1]==0&&s[j]<s[i])||dp[i+1][j-1]==1) res++;
			if((dp[i][j-2]==0&&s[j]<s[j-1])||dp[i][j-2]==1) res++;
			if(res>=2) suc1 = 1;
			
			res = 0;
			if((dp[i+1][j-1]==0&&s[i]>s[j])||dp[i+1][j-1]==2) res++;
			if((dp[i+2][j]==0&&s[i]>s[i+1])||dp[i+2][j]==2) res++;
			if(res>=2) suc2++;
			res = 0;
			if((dp[i+1][j-1]==0&&s[j]>s[i])||dp[i+1][j-1]==2) res++;
			if((dp[i][j-2]==0&&s[j]>s[j-1])||dp[i][j-2]==2) res++;
			if(res>=2) suc2++;
			
			if(suc1) dp[i][j] = 1;
			else if(suc2==2) dp[i][j] = 2;
			else dp[i][j] = 0;
		}
	}
	if(dp[1][n]==1) cout<<"Alice\n";
	if(dp[1][n]==0) cout<<"Draw\n";
	if(dp[1][n]==2) cout<<"Bob\n";
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>s+1;n = strlen(s+1);
		solve();
	}
	return 0;
}
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

总结：
多tm思考思考，把所学的知识结合起来，多动手看看，翻翻博客。