#PQJ393x2989. QOJ 393_2989

    ID: 2942 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:九省联合省选2018模拟

QOJ 393_2989

CCF NOI 2018 省队选拔赛 第一试一双木棋(chess) 一双木棋(chess) 【题目描述】 菲菲和牛牛在一块n 行m 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。 棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结 束。落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧 及上方的所有格子内都有棋子。 棋盘的每个格子上,都写有两个非负整数,从上到下第i 行中从左到右第j 列的格 子上的两个整数记作Aij 、Bij 。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲 菲的得分是所有有黑棋的格子上的Aij 之和,牛牛的得分是所有有白棋的格子上的Bi j 的和。 菲菲和牛牛都希望,自己的得分减去对方的得分得到的结果最大。现在他们想知 道,在给定的棋盘上,如果双方都采用最优策略且知道对方会采用最优策略,那么,最 终的结果如何。 【输入格式】 从文件chess.in 中读入数据。 输入第一行包含两个正整数n, m,保证n, m ≤10。 接下来n 行,每行m 个非负整数,按从上到下从左到右的顺序描述每个格子上的 第一个非负整数:其中第i 行中第j 个数表示Aij。 接下来n 行,每行m 个非负整数,按从上到下从左到右的顺序描述每个格子上的 第二个非负整数:其中第i 行中第j 个数表示Bij。 【输出格式】 输出到文件chess.out 中。 输出一个整数,表示菲菲的得分减去牛牛的得分的结果。 【样例1 输入】 2 3 2 7 3 9 1 2 3 7 2 2 3 1 第2 页 共10 页

CCF NOI 2018 省队选拔赛 第一试一双木棋(chess) 【样例1 输出】 2 【样例1 解释】 棋盘如图所示,双方都采用最优策略时,棋局如下: • 菲菲下在第1 行第1 列(这是第一步时唯一可以落子的格子); • 牛牛下在第1 行第2 列; • 菲菲下在第2 行第1 列; • 牛牛下在第1 行第3 列; • 菲菲下在第2 行第2 列; • 牛牛下在第2 行第3 列(这是这一步时唯一可以落子的格子); • 填满棋盘,游戏结束,盘面如下。 菲菲的得分为:2 + 9 + 1 = 12 ;牛牛的得分为:7 + 2 + 1 = 10 。 【样例2】 见选手目录下的chess/chess2.in 与chess/chess2.ans。 第3 页 共10 页

CCF NOI 2018 省队选拔赛 第一试一双木棋(chess) 【子任务】 对于所有的测试数据,n, m ≤10 ,Aij, Bij ≤100000。 对于编号为奇数的测试点,保证所有的Bij = 0 。 测试点 n = m = 1, 2, 3 2 2 4, 5, 6 3 3 7, 8 5 5 9, 10 8 8 11, 12 10 1 13, 14 10 2 15, 16 10 3 17, 18, 19, 20 10 10 第4 页 共10 页