本文共 1148 字，大约阅读时间需要 3 分钟。

题意

在一个有向无环图上，两个人分别从一个点出发，两人轮流从当前点沿着某条边移动，要求经过的边权不小于上一轮对方经过的边权（ASCII码），如果一方不能移动，则判负。两人都采取最优策略，求两人分别从每个点出发的胜负关系表。

分析

记忆化搜索。
f[x][y][v]表示现在两人分别在x,y，上一轮经过的边权为v时x是否能胜利（胜利为1，失败为0）。
考虑如何转移：
对于一条从x到u的边权为val的边，如果val>=v，则可以走这条边，算出f[y][u][val]，
如果f[y][u][val]为0，则说明在 f[x][y][v]这个状态下，有使得x胜利的方案，因为两个玩家都采取最优策略，这时x必定获胜。f[x][y][v]=1
如果f[y][u][val]为1，不要紧，主动权现在在处于x点的玩家手中，他可以不从这条路走，继续考察下一条x的出边。
如果无论如何处于x的玩家都赢不了，那么f[x][y][v]=0。
巧妙地博弈

代码

#include <bits/stdc++.h>using namespace std;#define ll long longint n,m;int u,v;char s[4];int dp[101][101][30];//dp[u][v][x]当前两人在u,v且上一轮边权为x时u的胜负vector<pair<int,int> >mp[101];int dfs(int u,int v,int x){	if(~dp[u][v][x]) return dp[u][v][x];	dp[u][v][x]=0;	int sz=mp[u].size();	for(int i=0;i<sz;++i)	{		pair<int,int>tmp=mp[u][i];		if(tmp.second>=x&&(!dfs(v,tmp.first,tmp.second))) {dp[u][v][x]=1;break;}	}	return dp[u][v][x];}int main(int argc, char const *argv[]){	scanf("%d %d",&n,&m);	for(int i=1;i<=m;++i)	{		scanf("%d %d %s",&u,&v,s);		mp[u].push_back(make_pair(v,s[0]-'a'));	}	memset(dp,-1,sizeof(dp));	for(int i=1;i<=n;++i){		for(int j=1;j<=n;++j)			if(dfs(i,j,0)) putchar('A');				else putchar('B');		puts("");	}	return 0;}