博弈dp
D. Letter Picking
题意：现有偶数长度的字符串 s 。Alice和Bob进行以下游戏：
- 每一回合，每人选择取走字符串首个字符，或取走末尾字符。
- 每人按获得顺序倒序排列他们取得的字符，得到各自的字符串。
- 最终得到的字符串字典序较小者胜利。相等则平局。
现两人足够聪明，求最终结果。
分析：设 \(dp_{l,r}\) 表示对于 \(l..r\) 的子字符串，其胜利者 1 表示Alice获胜， −1 表示Bob获胜， 0 表示平局。
如果 \(r−l+1=2\) ，若两个字符相同则平局，否则Alice获胜。
对于其他的情况：
- 如果，Alice选了 sl ，并且 dpl+1,r−1 和 dpl+2,r 均为 1 ，这表明在字符串的前几个字符中，Alice的字典序较小，所以不用比较后面字符，他一定能获胜。
- 同理，如果Alice选了 sr ，并且 dpl+1,r−1 和 dpl,r−2 均为 1 ，Alice获胜。
- 如果无论 Alice选择 sl 还是 sr ，对应的两个 dp 中都有 −1 ，则Bob获胜。
对应的代码：
if(min(dp[l+2][r], dp[l+1][r-1]) == 1) {dp[l][r] = 1; continue;}
if(min(dp[l][r-2], dp[l+1][r-1]) == 1) {dp[l][r] = 1; continue;}
if(min(dp[l+2][r], dp[l+1][r-1]) == -1 && min(dp[l][r-2], dp[l+1][r-1]) == -1) {dp[l][r] = -1; continue;}
除此以外的情况，先置 \(dp_{l,r}=−1\) ，然后讨论Alice如何将其转变为平局或获胜：
-
如果Alice选走 \(s_l\) 之后，\(dp_{l+1,r−1} 和 dp_{l+2,r}\) 中：
-
-
不存在 −1 。
-
不存在以下 Bob 能够获胜的情况：
-
- \(s_r<s_l,dp_{l+1,r−1}=0\)
- \(s_{l+1}<s_r,dp_{l+2,r}=0\)
-
-
那么Alice至少为平局。
-
更进一步地，如果Alice选走 sl 之后，dpl+1,r−1 和 dpl+2,r 中：
-
- 不存在 −1 。
- 不存在以下 Bob 能够能引向平局的情况：
- \(s_r=s_l,dp_{l+1,r−1}=0\)
- \(s_{l+1}=s_r,dp_{l+2,r}=0\)
-
那么Alice将获胜。
对于 \(s_r\) ，有类似结论。
代码比较麻烦，容易写错。
#include<bits/stdc++.h>
using namespace std;
int f[2010][2010];//1:Alice 0:平局 -1:Bob
int main()
{
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int len=s.size();
for(int i=0;i<len;i++) for(int j=0;j<len;j++) f[i][j]=0;
for(int l=2;l<=len;l+=2)
{
for(int i=0;i<len;i++)
{
int j=i+l-1;
if(l==2){
if(s[i]==s[j]) f[i][j]=0;
else f[i][j]=1;
continue;
}
if(f[i+1][j-1]==1&&f[i+2][j]==1) {f[i][j]=1;continue;} //选左边后手(Bob)无论如何都是输
if(f[i+1][j-1]==1&&f[i][j-2]==1) {f[i][j]=1;continue;} //选右边后手(Bob)无论如何都是输
if(min(f[i+1][j-1],f[i+2][j])==-1&&min(f[i+1][j-1],f[i][j-2])==-1) {f[i][j]=-1;continue;} //选哪边后手(Bob)都有办法赢
//剩下其余可能： 也就是说Alice不会必胜也不会必败，分类：Alice选左边或右边去试图追平或者取胜
f[i][j]=-1;//试图失败
//下面就是试图可能的情况
//选左边，且前面两人至少是追平的，有-1就不会选左边了 (因为正面情况太多所以考虑反面来))
int flag=0;
if(min(f[i+1][j-1],f[i+2][j])==0)//保证没有-1，可能有1
{
if(!(s[i]>s[j]&&f[i+1][j-1]==0)&&!(s[i]>s[i+1]&&f[i+2][j]==0)) //不存在Bob能取胜的情况
{
f[i][j]=0;
if(!(s[i]==s[j]&&f[i+1][j-1]==0)&&!(s[i]==s[i+1]&&f[i+2][j]==0)) f[i][j]=1;//不存在Bob能追平的情况
}
}
//选右边，且前面至少是追平的，有-1就不会选右边
if(min(f[i+1][j-1],f[i][j-2])==0&&!flag)//保证没有-1，但是可能有1
{
if(!(s[j]>s[i]&&f[i+1][j-1]==0)&&!(s[j]>s[j-1]&&f[i][j-2]==0))
{
f[i][j]=0;
if(!(s[j]==s[i]&&f[i+1][j-1]==0)&&!(s[j]==s[j-1]&&f[i][j-2]==0)) f[i][j]=1;
}
}
}
}
if(f[0][len-1]==1) cout<<"Alice\n";
else if(f[0][len-1]==0) cout<<"Draw\n";
else cout<<"Bob\n";
}
}
这题有个更好理解的版本：
定义 \(dp[i][j]\) 为Alice在执行最优策略下的结局（1表示胜，0表示平，-1表示败）
显然先手想要的结果的优先级是 ：\(1>0>-1\)
显然后手想要的结果的优先级是：\(-1>0>1\)
那么 Alice 就是对 dp 做max，Bob 就是对 dp 做min，这里思路跟 Rake it in 很像
然而每次选择无非有一下四种：
考虑转移：
无非就四种情况,只考虑前两次操作
- 先手拿 \(i\) ,后手拿 \(j\) , 从 \(dp[i+1][j-1]\) 转移
- 先手拿 \(i\) ,后手拿 \(i+1\) ，从\(dp[i+2][j]\) 转移
这两种情况后手的人有选择权，它会尽量的拿小的，故需要取两者的 Min ，设为 val1 。
- 先手拿 \(j\) ,后手拿 \(i\) , 从 \(dp[i+1][j-1]\) 转移
- 先手拿 \(j\) ,后手拿 \(j−1\) , 从 \(dp[i][j-2]\) 转移
后两种情况分析方法一样，取两者的 Min , 设为 \(val2\) 。
那么显然 \(dp[i][j]=max(val1,val2)\) ,因为先手者想要拿大的。
#include<bits/stdc++.h>
using namespace std;
int f[2010][2010];//1:Alice 0:平局 -1:Bob
string s;
int calc(int l,int r,int x,int y)//计算结果的函数：Alice选了x，Bob选了y
{
if(f[l][r]!=0) return f[l][r];//如果前面都是平局，那选什么不影响结果
if(s[x]<s[y]) return 1;
if(s[x]==s[y]) return 0;
return -1;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>s;
int len=s.size();
for(int i=0;i<len;i++) for(int j=0;j<len;j++) f[i][j]=0;
for(int l=2;l<=len;l++)
{
for(int i=0;i+l-1<len;i++)
{
int j=i+l-1;
if(l==2)
{
f[i][j]=(s[i]==s[j])? 0:1;
}else{
f[i][j]=max(min(calc(i+1,j-1,i,j),calc(i+2,j,i,i+1)),min(calc(i+1,j-1,j,i),calc(i,j-2,j,j-1)));
}
}
}
if(f[0][len-1]==1) cout<<"Alice\n";
else if(f[0][len-1]==0) cout<<"Draw\n";
else cout<<"Bob\n";
}
}