09 区间DP的博弈论模型： Letter Picking

区间DP的博弈论模型： Letter Picking

Letter Picking

题面翻译

题目描述

Alice 和 Bob 在玩游戏。

给出一个长度为偶数的，非空的且仅含小写字母的字符串 $s$。每个玩家还拥有一个初始为空的字符串。

Alice 先手，两名玩家交替行动。在一次行动中，玩家可以取 $s$ 首或尾字符，将其从 $s$ 中移除后加入到自己的字符串的 最前面。

当 $s$ 为空时游戏结束，拥有字典序更小的字符串的玩家获胜。若两名玩家的字符串相等则平局。

若 Alice 和 Bob 都足够聪明，判断谁会取胜，或者游戏为平局。

数据组数 $t\leq 10^3$，$\sum|s|\leq 2\times 10^3$。保证所有输入的 $|s|$ 长度都为偶数。

题目描述

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 $a_j = b_j$ for all $j < i$ and $a_i < b_i$ .

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)?

输入格式

The first line contains a single integer $t$ ( $1 \le t \le 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$ .

输出格式

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”.

样例 #1

样例输入 #1

2
forces
abba

样例输出 #1

Alice
Draw

提示

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

1. Alice picks the first letter in $s$ : $s=$ “orces”, $a=$ “f”, $b=$ “”;
2. Bob picks the last letter in $s$ : $s=$ “orce”, $a=$ “f”, $b=$ “s”;
3. Alice picks the last letter in $s$ : $s=$ “orc”, $a=$ “ef”, $b=$ “s”;
4. Bob picks the first letter in $s$ : $s=$ “rc”, $a=$ “ef”, $b=$ “os”;
5. Alice picks the last letter in $s$ : $s=$ “r”, $a=$ “cef”, $b=$ “os”;
6. 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.

定义状态：

对于区间i~j，博弈后的结果，记1为先手胜，0为先手平，-1为先手负

考虑先手：

以上为先手必获胜的结果，当先手出招时候，后手想使用反制手段，但是发现后手的每一种选择都是使结果导向先手方胜利，那么后手方没办法只能输；

接下来讨论先手出招，但后手通过反制手段，但因为选择当中没有使后手方获胜的情况，但存在若干个平手的情况，于是后手方退而求其次，使最终结果导向平局的情况；

当然这里讨论的是先手不输的情况，先手不输的情况包括先手赢和先手平两种，如果用if+先手赢+else if+先手不输 来把先手赢的情况再第二种情况之前拒之门外，那么第二种情况就是先手不输的情况

即为

附上代码：

#include <iostream>
#include <string.h>
#include <unordered_map>
#include <queue>
using namespace std;
#define int long long
int dp[2005][2005] = {0};
int solve(string s)
{
    int n = s.size() - 1;
    for (int i = 1, j = 2; j <= n; i++, j++) // 1 start
    {
        if (s[i] == s[j])
            dp[i][j] = 0;
        else
            dp[i][j] = 1;
    }
    for (int k = 2; 2 * k <= n; k++)
        for (int i = 1, j = 2 * k; j <= n; i++, j++)
        {
            if ((s[i] < s[i + 1] && dp[i + 2][j] == 0 || dp[i + 2][j] == 1) 
            && (dp[i + 1][j - 1] == 0 && s[i] < s[j] || dp[i + 1][j - 1] == 1)  
            || (s[j] < s[j - 1] && dp[i][j - 2] == 0 || dp[i][j - 2] == 1)
            && (dp[i + 1][j - 1] == 0 && s[j] < s[i] || dp[i + 1][j - 1] == 1))
            {
                dp[i][j] = 1;
            }
            else if
            (((s[i] <= s[i + 1] && dp[i + 2][j] == 0 || dp[i + 2][j] == 1) 
            && (dp[i + 1][j - 1] == 0 && s[i] <= s[j] || dp[i + 1][j - 1] == 1))
            || (s[j] <= s[j - 1] && dp[i][j - 2] == 0 || dp[i][j - 2] == 1) 
            && (dp[i + 1][j - 1] == 0 && s[j] <= s[i] || dp[i + 1][j - 1] == 1))
            {
                dp[i][j] = 0;
            }
            else
                dp[i][j] = -1;
        }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=n;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    return dp[1][n];
}
signed main(void)
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string temp, s = "0";
        cin >> temp;
        s += temp;
        int ans = solve(s);
        if (ans == 0)
            cout << "Draw" << endl;
        if (ans == 1)
            cout << "Alice" << endl;
        if (ans == -1)
            cout << "Bob" << endl;
    }

    return 0;
}