一双木棋(chess)
一双木棋(chess)
题目描述
菲菲和牛牛在一块 nn 行 mm 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。
棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。
棋盘的每个格子上,都写有两个非负整数,从上到下第 ii 行中从左到右第 jj 列的格子上的两个整数记作 A_{i,j}Ai,j、B_{i,j}Bi,j。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲菲的得分是所有有黑棋的格子上的 A_{i,j}Ai,j 之和,牛牛的得分是所有有白棋的格子上的 B_{i,j}Bi,j 的和。
菲菲和牛牛都希望,自己的得分减去对方的得分得到的结果最大。现在他们想知道,在给定的棋盘上,如果双方都采用最优策略且知道对方会采用最优策略,那么,最终的结果如何。
输入格式
从标准输入中读入数据。
输入第一行包含两个正整数 n, mn,m,保证 n, m \leq 10n,m≤10。 接下来 nn 行,每行 mm 个非负整数,按从上到下从左到右的顺序描述每个格子上的第一个非负整数:其中第 ii 行中第 jj 个数表示 A_{i,j}Ai,j。
接下来 nn 行,每行 mm 个非负整数,按从上到下从左到右的顺序描述每个格子上的第二个非负整数:其中第 ii 行中第 jj 个数表示 B_{i,j}Bi,j。
输出格式
输出到标准输出中。
输出一个整数,表示菲菲的得分减去牛牛的得分的结果。
样例
样例输入
2 3
2 7 3
9 1 2
3 7 2
2 3 1
样例输出
2
样例解释
棋盘如图所示,双方都采用最优策略时,棋局如下:
- 菲菲下在第 11 行第 11 列(这是第一步时唯一可以落子的格子);
- 牛牛下在第 11 行第 22 列;
- 菲菲下在第 22 行第 11 列;
- 牛牛下在第 11 行第 33 列;
- 菲菲下在第 22 行第 22 列;
- 牛牛下在第 22 行第 33 列(这是这一步时唯一可以落子的格子);
- 填满棋盘,游戏结束,盘面如下。
菲菲的得分为:2 + 9 + 1 = 122+9+1=12;牛牛的得分为:7 + 2 + 1 = 107+2+1=10。
数据范围与提示
对于所有的测试数据,n, m \leq 10, A_{i,j}, B_{i,j} \leq 100000n,m≤10,Ai,j,Bi,j≤100000。
对于编号为奇数的测试点,保证所有的 B_{i,j} = 0Bi,j=0。
测试点 | n=n= | m=m= |
---|---|---|
1,2,31,2,3 | 22 | 22 |
4,5,64,5,6 | 33 | 33 |
7,87,8 | 55 | 55 |
9,109,10 | 88 | 88 |
11,1211,12 | 1010 | 11 |
13,1413,14 | 1010 | 22 |
15,1615,16 | 1010 | 33 |
17,18,19,2017,18,19,20 | 1010 | 1010 |
来源
CCF 2018省选Day1
Solution
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#define ll unsigned long long
#define p 793999
using namespace std;
int n,m,a[][],b[][],tmp[];
unordered_map<ll,int>f,g,s[];
ll get(){
ll H=;
for(int i=;i<=n;i++){
H=H*p+tmp[i];
}
for(int i=;i<=m;i++)s[i][H]=tmp[i];
return H;
}
void dfs(int x,ll k){
if(x==n*m+){f[k]=;return;}
if(g[k])return ;g[k]=;
for(int i=;i<=m;i++)tmp[i]=s[i][k];
int Mx=-1e9,Mi=1e9;
if(tmp[]<m){
tmp[]++;ll nx=get();dfs(x+,nx);
Mx=max(Mx,f[nx]+a[][tmp[]]);
Mi=min(Mi,f[nx]-b[][tmp[]]);
tmp[]--;
}
for(int i=;i<=n;i++){
if(tmp[i]<tmp[i-]){
tmp[i]++;ll nx=get();dfs(x+,nx);
Mx=max(Mx,f[nx]+a[i][tmp[i]]);
Mi=min(Mi,f[nx]-b[i][tmp[i]]);
tmp[i]--;
}
}
if(x&)f[k]=Mx;else f[k]=Mi;
}
int main(){
cin>>n>>m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)scanf("%d",&b[i][j]);
dfs(,);
cout<<f[]<<endl;
return ;
}
最新文章
- 从DOM操作看Vue&;React的前端组件化,顺带补齐React的demo
- 【代码笔记】iOS-日历
- C++ 生成 dll 和调用 dll 的方法实例(转)
- Hibernate的关联映射——单向N-1关联
- eclipse系列: Cannot change version of project facet Dynamic web的解决方法
- 学习记录013-NFS相关知识点
- 超好用文件对比工具 – Beyond Compare
- BZOJ 1455: 罗马游戏( 配对堆 + 并查集 )
- JSP具体条款——response对象
- ubuntu 禁用快捷键
- 基于Unity&#183;UGUI实现的RecycleList循环列表UI容器
- 深入理解Java类加载器(1):Java类加载原理解析
- Django学习笔记(9)—— 开发用户注册与登录系统
- encodeURIComponent编码与解码
- 上网爱快?EasyRadius FOR 爱快V2接口测试版正式推出,欢迎广大爱迷们测试噢
- [转载]localStorage使用总结
- 第 6 章 存储 - 042 - 用 volume container 共享数据
- Iscloc用法笔记
- Flume source 支持的type类型
- kettle开源项目部署文档
热门文章
- java 虚方法。 后面new 那个类, 就调用哪个类的方法 ,而非定义类的方案。 关于父子 类的 呵呵
- LeetCode 337. House Robber III 动态演示
- vs2010修改的内容在浏览器页面不变怎么办
- python字典、字符串(json串)、字节串之间的转化
- DS-哈希表浅析
- Cookie/Session/Local Storage/IndexedDB
- express框架中router组件的app.use和app.get
- Linux知识-不断更新
- python常用函数 S
- [Luogu2365]任务安排(斜率优化)