P4363 [九省联考 2018] 一双木棋 chess

一、分析

"一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子" \(\Rightarrow\) 棋盘上的棋子呈阶梯状 \(\Rightarrow\) 相当于往右走 m 步，往上走 n 步，状态数只有 \({C_{n+m}^n}\)

可以直接暴力 11 进制状压，用 map 存储，记忆化搜索即可

二、实现

设差值为 \(d\) = 菲菲得分 - 牛牛得分

菲菲选时：\(d+=a[i][j]\)

牛牛选时：\(d-=b[i][j]\)

设 \(w=0\) 时，表示菲菲选，\(w=1\) 时表示牛牛选

\(w=1\)，使 \(d\) 尽可能大

\(w=1\)，使 \(d\) 尽可能小

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,a[15][15],b[15][15],ed;
map<int,bool> vis;
map<int,int> ans;
int dfs(int x,int w){if(x==ed) return 0;if(vis[x]) return ans[x];vis[x]=1;int p=1,c[15];int tmp=x;int sum;if(w) sum=inf;else sum=-inf;c[0]=inf;for(int i=1;i<=n;i++){c[i]=tmp%11;tmp/=11;}if(w){for(int i=1;i<=n;i++){if(c[i]<min(c[i-1],m))sum=min(sum,dfs(x+p,w^1)-b[i][c[i]+1]);p*=11;}}else{for(int i=1;i<=n;i++){if(c[i]<min(c[i-1],m))sum=max(sum,dfs(x+p,w^1)+a[i][c[i]+1]);p*=11;}}ans[x]=sum;return sum;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>a[i][j];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>b[i][j];}for(int i=1;i<=n;i++) ed=ed*11+m;cout<<dfs(0,0)<<'\n';return 0;
}