codeforce 459 DIV2 D题

 题意
   在一个DAG上面有N个点M条边，每一条边上都有一个小写字母。两个人Max and Lucas 每个人一颗棋子，两个人轮流行棋，当前这一步选择的路上面的字母必须大于等于上一步路上面的字母，当轮到一个人她无法行棋时她便输了。每个人行棋时走会走最优情况。输出所有两个人初始位置的输赢情况。

分析

  记忆搜索；dp[u][v][c]当前先手在点u,后手在点v，能走的字母大于等于c；先手胜利则dp[u][v][c]=1否则dp[u][v][c]=0;
   若G[u][x]=c2,且c2>=c,则if(dp[v][x][c2]==0),dp[u][v][c]=1；
   其实很好理解当前先手在u,后手在v，下一步先手走到x时，那么先手变后手，后手变前手。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100+10;
int n,m;
char G[maxn][maxn];
int dp[maxn][maxn][28];
int dfs(int u,int v,char c){
    if(dp[u][v][c-'a']!=-1)
        return dp[u][v][c-'a'];
    for(int i=1;i<=n;i++){
        if(G[u][i]>=c)
            if(dfs(v,i,G[u][i])==0)return dp[u][v][c-'a']=1;
    }
    return dp[u][v][c-'a']=0;
}
int main(){
    memset(G,0,sizeof(G));
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++){
        scanf("%d%d %c",&a,&b,&c);
        G[a][b]=c;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dfs(i,j,'a');
        }
    }
    for(int i=1;i<=n;i++){
        if(i!=1)cout<<""<<endl;
        for(int j=1;j<=n;j++){
            if(dp[i][j][0])
                cout<<"A";
            else
                cout<<"B";
        }
    }
return 0;
}