题目名称 2886. [九省联考 2018] 一双木棋
输入输出 chess2018.in/out
难度等级 ★★★☆
时间限制 2000 ms (2 s)
内存限制 512 MiB
测试数据 20
题目来源 GravatarAAAAAAAAAA 于2018-04-09加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:12, 提交:20, 通过率:60%
Gravatar_Itachi 100 0.100 s 5.29 MiB C++
GravatarHzoi_moyi 100 0.309 s 8.77 MiB C++
GravatarBFZD 100 2.215 s 0.30 MiB C++
GravatarCSU_Turkey 100 2.388 s 11.75 MiB C++
Gravatar徐心雨 100 2.504 s 0.31 MiB C++
Gravatar徐心雨 100 2.512 s 0.32 MiB C++
Gravatar徐心雨 100 2.518 s 0.31 MiB C++
Gravatar徐心雨 100 2.529 s 0.31 MiB C++
GravatarNarcissus 100 3.045 s 0.14 MiB C++
GravatarShirry 100 3.207 s 0.26 MiB C++
关于 一双木棋 的近10条评论(全部评论)

2886. [九省联考 2018] 一双木棋

★★★☆   输入文件:chess2018.in   输出文件:chess2018.out   简单对比
时间限制:2 s   内存限制:512 MiB

【题目描述】

菲菲和牛牛在一块 $n$ 行 $m$ 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。

棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都棋子。

棋盘的每个格子上,都写有两个非负整数,从上到下第 $i$ 行中从左到右第 $j$ 列的格 子上的两个整数记作 $A_{ij}$ 、$B_{ij}$ 。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲 菲的得分是所有有黑棋的格子上的 $A_{ij}$ 之和,牛牛的得分是所有有白棋的格子上的 $B_{ij}$ 的和。

菲菲和牛牛都希望,自己的得分减去对方的得分得到的结果最大。现在他们想知道, 在给定的棋盘上,如果双方都采用最优策略且知道对方会采用最优策略,那么,最终的结果如何。

【输入格式】

从文件 $chess.in$ 中读入数据。

输入第一行包含两个正整数 $n, m$,保证 $n, m ≤ 10$。

接下来 $n$ 行,每行 $m$ 个非负整数,按从上到下从左到右的顺序描述每个格子上的第一个非负整数:其中第 $i$ 行中第 $j$ 个数表示 $A_{ij}$。

接下来 $n$ 行,每行 $m$ 个非负整数,按从上到下从左到右的顺序描述每个格子上的第二个非负整数:其中第 $i$ 行中第 $j$ 个数表示 $B_{ij}$。

【输出格式】

输出到文件 chess.out 中。 输出一个整数,表示菲菲的得分减去牛牛的得分的结果。

【样例输入】

2 3
2 7 3
9 1 2
3 7 2
2 3 1

【样例输出】

2

【提示】

【子任务】

对于所有的测试数据,$n,m≤10$,$A_{ij},B_{ij} ≤100000$。

对于编号为奇数的测试点,保证所有的 $B_{ij} = 0$ 。

【来源】