CodeForces 1728D Letter Picking 题解

发表于 更新于 分类于 ， 本文字数： 1.7k 阅读时长 ≈ 3 分钟

题目传送门

Solution

题意

给定一个长度为偶数 ($n < 20000$)、均为小写字母的字符串，Alice 和 Bob 轮流从中取一个字母，可以选择从左面取一个，也可以选择从右面取，追加到自己已有的字符串末尾（两人初始 r 字符串为空）。字符串被取空后，两个自己的字符串字典序小的胜利。

思路

设字符串长度为 $n$，我们使用 $dp [l][r]$ 表示当字符串剩余 $s [l \dots r-1]$ （不含 $r$）时胜负情况，则 $dp [0][n]$ 即为答案。

我们使用 $dp [l][r] < 0$ 表示 Alice 胜， $dp [l][r] = 0$ 表示平局， $dp [l][r] > 0$ 表示 Bob 胜。

易得，$dp [i][i] = 0$。 我们要想求 $dp [l][r]$，则要知道其更小范围（少两个字母）的 $dp$ 数据，即 $dp [l+2][r]$、$dp [l+1][r-1]$、$dp [l+2][r]$ 的值。根据这三个更小范围的 $dp$ 值，及 Alice、Bob 拿的两个字母的大小，我们可以确定出 $dp [l][r]$ 的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2010;
const int INF = 0x3f3f3f3f;

int T;
string s;

int dp[MAXN][MAXN];

int cmp(char a, char b)
{
    return a-b;
}

int main()
{
    cin >> T;

    while(T--)
    {
        memset(dp, 0, sizeof(dp));

        cin >> s;
        int n = s.length();
        
        for(int len=2; len<=n; len+=2)
        {
            for(int l=0; l<=n-len; l++)
            {
                int r = l+len;
                
                dp[l][r] = INF;

                // Alice 拿左边字母的情况
                {
                    int res = -INF;

                    // Alice 拿左边字母、Bob 拿右边字母
                    if(dp[l+1][r-1] == 0)
                        res = max(res, cmp(s[l], s[r-1]));
                    else
                        res = max(res, dp[l+1][r-1]);

                    // Alice 拿左边字母、Bob 拿左边字母
                    if(dp[l+2][r] == 0)
                        res = max(res, cmp(s[l], s[l+1]));
                    else
                        res = max(res, dp[l+2][r]);
                    
                    dp[l][r] = min(dp[l][r], res);
                }

                // Alice 拿右边字母的情况
                {
                    int res = -INF;

                    // Alice 拿右边字母的情况、Bob 拿左边字母
                    if(dp[l+1][r-1] == 0)
                        res = max(res, cmp(s[r-1], s[l]));
                    else
                        res = max(res, dp[l+1][r-1]);
                    
                    // Alice 拿右边字母的情况、Bob 拿右边字母
                    if(dp[l][r-2] == 0)
                        res = max(res, cmp(s[r-1], s[r-2]));
                    
                    dp[l][r] = min(dp[l][r], res);
                }
            }
        }

        if(dp[0][n] < 0)
            cout << "Alice\n";
        else if(dp[0][n] == 0)
            cout << "Draw\n";
        else
            cout << "Bob\n";
    }
    return 0;
}

感悟

这种题目，我们可以较为轻松的知道小范围的答案（如两个字母），这样我们就可以再转移到下一个状态（四个字母），如此扩下去。以长度做为 dp 的最外层循环，一步步推导出答案。