CF917B MADMAX

題意：

Alice和Bob有一個n個點m條邊的DAG，每條邊上有一個小寫英文字母表示權值，Alice和Bob每人有一個棋子，每個人放在一個節(jié)點上（可以放在同一個節(jié)點上）。 第一輪Alice可以沿一條邊把棋子移到一個相鄰的節(jié)點上，之后Bob沿一條邊移動棋子，以此類推，規(guī)則規(guī)定：每一次移動經過的邊的ASCII碼單調不降（即，若Alice沿’c’走了一步,Bob只能沿’c’或’c’之后的字母走，然后Alice又要沿Bob走過的字母之后的字母走…）。不能走的人輸掉這盤游戲。 現在他們想知道，給定初始位置，兩人都按最優(yōu)策略，誰會贏？

題解：

枚舉起點，正常模擬博弈過程
sg[x][y][kw]:先手為x，后手為y，字母限制不超過kw的這個狀態(tài)的sg值
如果sg==0說明先手輸，sg=1說明先手贏
v是u的下一個狀態(tài)
如果全部sg[v]是1，sg[u]為0
如果存在sg[v]是0，sg[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

代碼：

#include<bits/stdc++.h> #define INF (1<<25) #define MAXN 105 #define LL long long using namespace std;int N,M;struct edge{int v,w;edge(int v=0, int w=0):v(v), w(w){} };vector<edge> 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 k=0;k<adj[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(){cin>>N>>M;int u,v;char c;for(int i=1;i<=M;i++){cin>>u>>v>>c;adj[u].push_back(edge(v,c-'a'));}memset(sg,-1,sizeof(sg));//初始化為-1 for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){if(dfs(i,j,0)) cout<<"A";else cout<<"B";}cout<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的CF917B MADMAX的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。