Description

菲菲和牛牛在一塊n 行m 列的棋盤上下棋，菲菲執黑棋先手，牛牛執白棋后手。
棋局開始時，棋盤上沒有任何棋子，兩人輪流在格子上落子，直到填滿棋盤時結
束。落子的規則是：一個格子可以落子當且僅當這個格子內沒有棋子且這個格子的左側
及上方的所有格子內都有棋子。
棋盤的每個格子上，都寫有兩個非負整數，從上到下第i 行中從左到右第j 列的格
子上的兩個整數記作Ai j 、Bi j 。在游戲結束后，菲菲和牛牛會分別計算自己的得分：菲
菲的得分是所有有黑棋的格子上的Ai j 之和，牛牛的得分是所有有白棋的格子上的Bi j
的和。
菲菲和牛牛都希望，自己的得分減去對方的得分得到的結果最大。現在他們想知
道，在給定的棋盤上，如果雙方都采用最優策略且知道對方會采用最優策略，那么，最
終的結果如何。

Input

從文件chess.in 中讀入數據。
輸入第一行包含兩個正整數n;m，保證n;m <=10。
接下來n 行，每行m 個非負整數，按從上到下從左到右的順序描述每個格子上的
第一個非負整數：其中第i 行中第j 個數表示Ai j。
接下來n 行，每行m 個非負整數，按從上到下從左到右的順序描述每個格子上的
第二個非負整數：其中第i 行中第j 個數表示Bi j。

Output

輸出到文件chess.out 中。
輸出一個整數，表示菲菲的得分減去牛牛的得分的結果。

Sample Input

【樣例1 輸入】
2 3
2 7 3
9 1 2
3 7 2
2 3 1

Sample Output

【樣例1 輸出】
2

Data Constraint

Hint

棋盤如圖所示，雙方都采用最優策略時，棋局如下：
? 菲菲下在第1 行第1 列（這是第一步時唯一可以落子的格子）；
? 牛牛下在第1 行第2 列；
? 菲菲下在第2 行第1 列；
? 牛牛下在第1 行第3 列；
? 菲菲下在第2 行第2 列；
? 牛牛下在第2 行第3 列（這是這一步時唯一可以落子的格子）；
? 填滿棋盤，游戲結束，盤面如下。

菲菲的得分為：2 + 9 + 1 = 12 ；牛牛的得分為：7 + 2 + 1 = 10 。

Solution

• 首先，我們發現下棋的地方形如：
  ####-
  ###–
  ##—
  ##—
  #—-

• 即盤踞在左上角的一整塊。

• 于是考慮記憶化搜索+Hash，狀態就是每一行填了幾個棋子，用Hash壓起來（11進制）。

• 之后判斷此時改哪一方走，若是先手一方走，則：

  ans=max(ans,dfs(s)+a[i][j])

• 若是后手方，則：

  ans=min(ans,dfs(s)?b[i][j])

• 注意能轉移時下一行的棋子數要大于上一行的棋子數。

• 有用狀態只有 C1020 種。

Code

#include<cstdio> #include<map> #include<cctype> using namespace std; typedef long long LL; const int N=11,inf=1e9; int n,m; int a[N][N],b[N][N]; map<LL,int>mp; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void init() {n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) b[i][j]=read();LL all=0;for(int i=1;i<=n;i++) all=all*N+m;mp[all]=0; } inline LL hash(int *f) {LL sum=0;for(int i=1;i<=n;i++) sum=sum*N+f[i];return sum; } int dfs(LL s) {if(mp.count(s)) return mp[s];int f[N];f[0]=m;LL x=s;int pd=0,ans;for(int i=n;i;i--) pd+=f[i]=x%N,x/=N;if(pd&1){ans=inf;for(int i=1;i<=n;i++)if(f[i]<f[i-1]){f[i]++;ans=min(ans,dfs(hash(f))-b[i][f[i]]);f[i]--;}}else{ans=-inf;for(int i=1;i<=n;i++)if(f[i]<f[i-1]){f[i]++;ans=max(ans,dfs(hash(f))+a[i][f[i]]);f[i]--;}}return mp[s]=ans; } int main() {init();printf("%d",dfs(0));return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5637. 【NOI2018模拟4.8】一双木棋的全部內容，希望文章能夠幫你解決所遇到的問題。

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