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

    ID: 4775 远端评测题 1000ms 500MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>动态规划,dp搜索2018各省省选状态压缩,状压

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

题目描述

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

棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。

落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。

棋盘的每个格子上,都写有两个非负整数,从上到下第 ii 行中从左到右第 jj 列的格子上的两个整数记作 ai,ja_{i,j}bi,jb_{i,j}

在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲菲的得分是所有有黑棋的格子上的 ai,ja_{i,j} 之和,牛牛的得分是所有有白棋的格子上的 bi,jb_{i,j} 的和。

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

输入格式

第一行有两个整数,分别表示棋盘的行数 nn 和列数 mm
22 到第 (n+1)(n + 1) 行,每行 mm 个整数,第 (i+1)(i + 1) 行的第 jj 个整数表示 ai,ja_{i, j}
(n+2)(n + 2) 到第 (2n+1)(2n + 1) 行,每行 mm 个整数,第 (n+i+1)(n + i + 1) 行的第 jj 个整数表示 bi,jb_{i, j}

输出格式

输出一行一个整数,表示菲菲的得分减去牛牛的得分的结果。

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

2

提示

样例 1 说明

棋盘如图所示,双方都采用最优策略时,棋局如下:

  • 菲菲下在第 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

数据规模与约定

各测试点信息如下表。

  • 对于编号为奇数的测试点,保证 bi,j=0b_{i, j} = 0
  • 对于全部的测试点,保证 1n,m101 \leq n, m \leq 100ai,j,bi,j1050 \leq a_{i, j}, b_{i, j} \leq 10^5