[CF917B] MADMAX - 博弈论,dp,记忆化搜索

有一个 DAG，每条边上有一个小写英文字母表示权值，Alice 和 Bob 每人有一个棋子，各放在一个节点上（可以放在同一个节点上）。第一轮 Alice 可以沿一条边把棋子移到一个相邻的节点上，之后 Bob 沿一条边移动棋子，以此类推。规则规定每一次移动经过的边的 ASCII 码单调不降。不能走的人输。对于所有的初始位置，两人都按最优策略，问谁会赢。\(n\leq 100\)

Solution

设 \(f[i][j][k]\) 表示先手位于 \(i\)，后手位于 \(j\)，边权为 \(k\) 对应的胜负情况

对于 \(i\) 所有出点 \(q\)，状态转移为 \(f[j][q][w]\)

如果至少存在一个 \(q\) 使得 \(f[j][q][w]\) 为 \(0\)，那么 \(f[i][j][k]\) 为 \(1\)，否则为 \(0\)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 105;

int n,m,f[N][N][N];
struct edge {int v,w;};
vector <edge> g[N];

int dfs(int i,int j,int k) {
    if(f[i][j][k]!=-1) return f[i][j][k];
    f[i][j][k]=0;
    for(edge e:g[i]) {
        int q=e.v, w=e.w;
        if(w<k) continue;
        if(!dfs(j,q,w)) return f[i][j][k]=1;
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int t1,t2;
        char t3;
        cin>>t1>>t2>>t3;
        g[t1].push_back({t2,t3-‘a‘});
    }
    memset(f,0xff,sizeof f);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cout<<(dfs(i,j,0)?‘A‘:‘B‘);
        }
        cout<<endl;
    }
}

[CF917B] MADMAX - 博弈论,dp,记忆化搜索

原文：https://www.cnblogs.com/mollnn/p/12587370.html