外贸网站英文版,河南最新新闻头条,查企业不要钱的软件,app网站建设哪家好CF917B MADMAX
题意#xff1a;
Alice和Bob有一个n个点m条边的DAG#xff0c;每条边上有一个小写英文字母表示权值#xff0c;Alice和Bob每人有一个棋子#xff0c;每个人放在一个节点上#xff08;可以放在同一个节点上#xff09;。 第一轮Alice可以沿一条边把棋子移…CF917B MADMAX
题意
Alice和Bob有一个n个点m条边的DAG每条边上有一个小写英文字母表示权值Alice和Bob每人有一个棋子每个人放在一个节点上可以放在同一个节点上。 第一轮Alice可以沿一条边把棋子移到一个相邻的节点上之后Bob沿一条边移动棋子以此类推规则规定每一次移动经过的边的ASCII码单调不降即若Alice沿’c’走了一步,Bob只能沿’c’或’c’之后的字母走然后Alice又要沿Bob走过的字母之后的字母走…。不能走的人输掉这盘游戏。 现在他们想知道给定初始位置两人都按最优策略谁会赢
题解
枚举起点正常模拟博弈过程 sg[x][y][kw]:先手为x后手为y字母限制不超过kw的这个状态的sg值 如果sg0说明先手输sg1说明先手赢 v是u的下一个状态 如果全部sg[v]是1sg[u]为0 如果存在sg[v]是0sg[u]为1 上面这两个条件怎么实现呢 我们令sg[u]为0然后去找v,如果有一个v使得sg[v]是0说明sg[v]1 当不能走时即输掉比赛此时sg为0 dfs模拟过程记忆化搜索dp实现 复杂度O(26 * N^2 26 * N * M)
26 * N * N是枚举起点 26 * N * M是dfs
代码
#includebits/stdc.h
#define INF (125)
#define MAXN 105
#define LL long long
using namespace std;int N,M;struct edge{int v,w;edge(int v0, int w0):v(v), w(w){}
};vectoredge adj[MAXN];int sg[MAXN][MAXN][26];
//sg 0/1 lose/win
//sg[u] 0, if all sg[v] 1
//sg[u] 1, if some sg[v] 0 bool dfs(int x, int y, int kw){if(sg[x][y][kw] ! -1) return sg[x][y][kw];sg[x][y][kw] 0;int v,w;for(int k0;kadj[x].size();k){v adj[x][k].v;w adj[x][k].w;if(w kw) continue;//必须满足字母非上升序列 if(dfs(y,v,w)0){sg[x][y][kw] 1;break;}}return sg[x][y][kw];
}int main(){cinNM;int u,v;char c;for(int i1;iM;i){cinuvc;adj[u].push_back(edge(v,c-a));}memset(sg,-1,sizeof(sg));//初始化为-1 for(int i1;iN;i){for(int j1;jN;j){if(dfs(i,j,0)) coutA;else coutB;}coutendl;}return 0;
}
