bzoj 5248: [2018多省省队联测]一双木棋

Description

菲菲和牛牛在一块n行m列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。棋局开始时，棋盘上没有任何棋子，
两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且
这个格子的左侧及上方的所有格子内都有棋子。
棋盘的每个格子上，都写有两个非负整数，从上到下第i行中从左到右第j列的格子上的两个整数记作Aij、Bij。在
游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的Aij之和，牛牛的得分是所
有有白棋的格子上的Bij的和。
菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都
采用最优策略且知道对方会采用最优策略，那么，最终的结果如何

Solution

维护一个轮廓线,设 \(c[i]\) 表示第 \(i\) 行可以放的位置
\(c[i]\) 是一个递减序列,而且 \(n\) 比较小,我们可以直接拿一个 \(long\,long\) 存下这个数组
然后用 \(map\) 记忆化这个搜索就行了

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=15,inf=1e9; int n,m,a[N][N],b[N][N],c[N]; inline ll hash(){ll ret=0;for(int i=1;i<=n;i++)ret=ret*11+c[i]-1;return ret; } inline void getc(ll S){for(int i=1;i<=n;i++)c[n-i+1]=S%11+1,S/=11; } map<ll,int>V; inline bool check(){for(int i=1;i<=n;i++)if(c[i]<=m)return false;return true; } inline int dfs(ll S){if(V.find(S)!=V.end())return V[S];getc(S);if(check())return V[S]=0;int ret=0,op=0,x;ll T;for(int i=1;i<=n;i++)op+=c[i]-1;op&=1;ret=op?inf:-inf;for(int i=1;i<=n;i++){if(c[i]<c[i-1]){c[i]++;T=hash();c[i]--;x=c[i];if(!op)ret=max(ret,a[i][x]+dfs(T));else ret=min(ret,-b[i][x]+dfs(T));getc(S);}}return V[S]=ret; } int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);c[0]=m+1;for(int i=1;i<=n;i++)c[i]=1;cout<<dfs(0)<<endl;return 0; }

转载于:https://www.cnblogs.com/Yuzao/p/8734601.html

总结

以上是生活随笔为你收集整理的bzoj 5248: [2018多省省队联测]一双木棋的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。