Codeforces 918D(博弈论+DAG图DP)

Codeforces 918D
题意:一个 DAG 图,边权是小写字母,两人玩游戏,他们起点分别是$i$和$j$节点,每次可以沿出边方向移动一格,前提是该边的字母大于等于上一轮移动经过的边的字母,不能移动的就输,问所有$i$和$j$为起点结果谁能赢。

设$dp(t,i,j)$为当前限制字母$t$下,先手在$i$, 后手在$j$时先手是否获胜。
那么直接记忆化搜索转移即可,注意交替先后手,如果当前后手无法移动则当前先手获胜。

知识点:博弈 DP 核心为先手后手状态 + 交替先手后手求解。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
int n, m, dp[30][MAXN][MAXN], ma[MAXN][MAXN];
int dfs(int t, int x, int y) {
if (dp[t][x][y] >= 0) return dp[t][x][y];
for (int i = 1; i <= n; i++)
if (ma[x][i] >= 0 && ma[x][i] >= t && !dfs(ma[x][i], y, i)) return dp[t][x][y] = 1;
return dp[t][x][y] = 0;
}
void clean() {
ms(ma, -1), ms(dp, -1);
}
int solve() {
clean();
char s[5];
for (int x, y, i = 1; i <= m; i++) scanf("%d%d%s", &x, &y, s), ma[x][y] = s[0] - 'a';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) dp[0][i][j] = dfs(0, i, j);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) if (dp[0][i][j]) printf("A"); else printf("B");
puts("");
}
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

------ 本文结束 ------