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

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

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

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

#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;
}