D. Letter Picking

思路：区间dp，令dp[i][j]表示从子串l~r中按规则取的输赢情况，dp[i][j]=1表示Alice赢，dp[i][j]=0表示平局，dp[i][j]=-1表示Bob赢。初始时若s[i]!=s[i+1]，则dp[i][i+1]=1，否则dp[i][i+1]=0。考虑转移，因为串长必须为偶数，因此考虑dp[i][j]如何由dp[i'][j']转移而来，假设Alice先选s[i]，则Bob只能选s[i+1]或s[j]，假设Bob选s[i+1]，则如果dp[i+2][j]=1的话，必定Alice赢，否则如果dp[i+2][j]=0的话，如果s[i]==s[i+1]，则平局，否则Alice赢。因为初始情况下dp[i'][j']必定不为-1，而转移过程中又不会出现结果为-1的情况，因此Bob必不可能赢。因此可以考虑平局的情况，剩下的情况就是Alice赢。若平局，则无论Alice第一步选s[i]或s[j]，Bob都有可能打平，即在Alice选s[i]或s[j]的情况下，Bob在他的两种选法中，必须至少有一种打平的情况出现才行。

代码：

void slove(){
   string s;
   cin>>s;
   int sz=s.size();
   int dp[sz][sz];
   mm(dp,0);
   _for(i,0,sz-1){
    if(s[i]!=s[i+1])dp[i][i+1]=1;
   }
   int dis=4;
   while(dis<=sz){
    _fore(i,0,sz-dis){
        int l=i,r=l+dis-1;
        if(((dp[l+2][r]==0&&s[l]==s[l+1])||(dp[l+1][r-1]==0&&s[l]==s[r]))&&((dp[l][r-2]==0&&s[r]==s[r-1])||(dp[l+1][r-1]==0&&s[l]==s[r])))dp[l][r]=0;
        else dp[l][r]=1;
    }
    dis+=2;
   }
    if(dp[0][sz-1]==1)cout << "Alice" << endl;
    else cout << "Draw" << endl;
}