博弈论dp模板题
首先我们可以先确定dp状态 dp[round][L][R][0/1]表示第round轮，现在字符串为[L~R],上一轮的人取了左边还是右边
然后发现round是可以由字符串L~R确定而来的，因为每一轮只删除一个数，因此可以优化round这维
我们令dp[L][R][0/1]=1为 Alice 赢，dp[L][R][0/1]=0为平局，dp[L][R][0/1]=-1为Bob胜利
对于Alice是先手，所以我们只需要ans尽量大即可：
if(round&1) //A的轮次 ans=max(dfs(L+1,R,0),dfs(L,R-1,1));
对于Bob是后手，所以每次都要都还要考虑 Alice 选了啥：
其实也就四种情况：
1.Alice选了L-1,Bob选了L
2.Alice选了L-1,Bob选了R
3.Alice选了R+1,Bob选了L
4.Alice选了R+1,Bob选了R
然后让ans尽可能小就行了
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second #define popcount __builtin_popcount const int N=2010; //const int M=; const int inf=1e9; //const ll INF=1e18; int T,n,dp[N][N][2]; char s[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int dfs(int L,int R,int op) { int round=n-(R-L+1)+1; if(dp[L][R][op]!=inf) return dp[L][R][op]; int ans; if(round&1) //A的轮次 ans=max(dfs(L+1,R,0),dfs(L,R-1,1)); else //B的轮次 { ans=inf; if(op==0) // A选了L-1的位置 { // B选了L的位置 if(dfs(L+1,R,0)==1) ans=min(ans,1); else if(dfs(L+1,R,0)==-1) ans=min(ans,-1); else { if(s[L-1]==s[L]) ans=min(ans,0); if(s[L-1]>s[L]) ans=min(ans,1); if(s[L-1]<s[L]) ans=min(ans,-1); } // B选了R的位置 if(dfs(L,R-1,1)==1) ans=min(ans,1); else if(dfs(L,R-1,1)==-1) ans=min(ans,-1); else { if(s[L-1]==s[R]) ans=min(ans,0); if(s[L-1]>s[R]) ans=min(ans,1); if(s[L-1]<s[R]) ans=min(ans,-1); } } else // A选了 R+1 的位置 { // B选了L的位置 if(dfs(L+1,R,0)==1) ans=min(ans,1); else if(dfs(L+1,R,0)==-1) ans=min(ans,-1); else { if(s[R+1]==s[L]) ans=min(ans,0); if(s[R+1]>s[L]) ans=min(ans,1); if(s[R+1]<s[L]) ans=min(ans,-1); } // B选了R的位置 if(dfs(L,R-1,1)==1) ans=min(ans,1); else if(dfs(L,R-1,1)==-1) ans=min(ans,-1); else { if(s[R+1]==s[R]) ans=min(ans,0); if(s[R+1]>s[R]) ans=min(ans,1); if(s[R+1]<s[R]) ans=min(ans,-1); } } } return dp[L][R][op]=ans; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); // ios::sync_with_stdio(0); // cin.tie(0); T=read(); while(T--) { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) dp[i][j][0]=dp[i][j][1]=inf; int op=dfs(1,n,0); if(op==1) puts("Alice"); else if(op==0) puts("Draw"); else if(op==-1) puts("Bob"); } return 0; }