Codeforces 918D/917B

传送门：http://codeforces.com/contest/918/problem/D

本题是一个组合游戏问题——DAG上的动态规划问题。

有一张有向无环图（DAG）。有两个玩家在这张图上进行一个游戏：初始时，玩家A、B各占据一个结点，之后轮流沿着有向边移动；移动时的边权是不下降的。无法移动者输。

请打印一个n×n矩阵，这个矩阵的元代表获胜方（A/B），其i行j列元的含义如下：玩家A的初始位置为结点i，玩家B的初始位置为结点j。

对于DAG上的组合游戏，可以考虑DP。

定义布尔变量dp(u,v,c)，代表当先手的初始位置为结点u，后手的初始位置为结点v，且上一次移动的边权为c时，先手是否能移动。则：

若存在有向边<u,x>，使得c≤cost<u,x>，且dp(v,x,cost<u,x>)=0，于是，一旦先手到达结点x后，后手将无法移动：于是先手必胜，即dp(u,v,c)=1；否则先手必败，即dp(u,v,c)=0。

参考程序如下：

#include <stdio.h>

#include <string.h>

#define MAX_N 101

#define MAX_C 26

int n, m;

int adj[MAX_N][MAX_N];

int dp[MAX_N][MAX_N][MAX_C];

int dfs(int u, int v, int c)

{

    if (dp[u][v][c] != -) return dp[u][v][c];

    for (int x = ; x <= n; x++) {

        if (adj[u][x] >= c && !dfs(v, x, adj[u][x]))

            return dp[u][v][c] = ;

    }

    return dp[u][v][c] = ;

}

int main(void)

{

    scanf("%d%d", &n, &m);

    memset(adj, -, sizeof(adj));

    memset(dp, -, sizeof(dp));

    while (m--) {

        int u, v;

        char ch;

        scanf("%d%d %c", &u, &v, &ch);

        adj[u][v] = ch - 'a';

    }

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= n; j++) {

            if (dfs(i, j, )) putchar('A');

            else putchar('B');

        }

        putchar('\n');

    }

    return ;

}

巴特西

Codeforces 918D/917B - MADMAX

最新文章

热门文章