Educational Codeforces Round 135 D. Letter Picking

Codeforces 区间DP

Alice and Bob are playing a game. Initially, they are given a non-empty string s, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string s, removes it from s and prepends (adds to the beginning) it to their own string.

The game ends when the string s becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string a is lexicographically smaller than a string b if there exists such position i that aj=bj for all j

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

Input
The first line contains a single integer t (1≤t≤1000) — the number of testcases.

Each testcase consists of a single line — a non-empty string s, consisting of lowercase Latin letters. The length of the string s is even.

The total length of the strings over all testcases doesn't exceed 2000.

Output
For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

Example
input

2
forces
abba

output

Alice
Draw

Note
One of the possible games Alice and Bob can play in the first testcase:

Alice picks the first letter in s: s="orces", a="f", b="";
Bob picks the last letter in s: s="orce", a="f", b="s";
Alice picks the last letter in s: s="orc", a="ef", b="s";
Bob picks the first letter in s: s="rc", a="ef", b="os";
Alice picks the last letter in s: s="r", a="cef", b="os";
Bob picks the remaining letter in s: s="", a="cef", b="ros".
Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

区间DP，贪心的策略有问题，但是可以看出Bob是无法获胜的，只需要判断Alice是否能赢

f[l][r]表示区间[l,r)上的胜负情况，若为true，则Alice赢，否则平局。
转移方式为从空串开始（f[l][r]=false），每个区间[l,r)可以从[l+1,r-1),[l+2,r),[l,r-2)转移，Alice可以决定第一下选左边的还是右边的字符，Bob可以选择第二下接着选左还是右，这就对应代码中的四个状态v，分别对应四种转移情况，而表达式f[l][r] = (vlr & vll) | (vrl & vrr);则说明Bob可以选择第二次选择中更为有利的一项（尽量平局，保持false），Alice可以选第一次选择中更有利的一项（保持true）。

#include <bits/stdc++.h>
using std::deque;
using std::greater;
using std::make_pair;
using std::pair;
using std::priority_queue;
using std::sort;
using std::vector;
const int MAXN = 2E3 + 7;
bool f[MAXN][MAXN];
char str[MAXN];
void solve() {
    scanf("%s", str);
    int n = strlen(str);
    for (int length = 0; length <= n; length += 2) {
        for (int l = 0; l < n; l++) {
            int r = l + length;
            if (r > n) {
                break;
            }
            if (r == l) {
                f[l][r] = 0;
                continue;
            }
            bool vlr =
                f[l + 1][r - 1] == 0 ? str[l] < str[r - 1] : f[l + 1][r - 1];
            bool vrl =
                f[l + 1][r - 1] == 0 ? str[l] > str[r - 1] : f[l + 1][r - 1];
            ;
            bool vll = f[l + 2][r] == 0 ? str[l] < str[l + 1] : f[l + 2][r];
            bool vrr = f[l][r - 2] == 0 ? str[r - 1] < str[r - 2] : f[l][r - 2];
            f[l][r] = (vlr & vll) | (vrl & vrr);
        }
    }
    if (f[0][n])
        puts("Alice");
    else
        puts("Draw");
}
int main() {
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int kase;
    scanf("%d", &kase);
    while (kase--) {
        solve();
    }
    return 0;
    return 0;
}