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

    • 443通过
    • 1.3K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 搜索 状态压缩,状压 各省省选 2018 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    菲菲和牛牛在一块n 行m 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。 棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。

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

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

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

    输入输出格式

    输入格式:

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

    输入第一行包含两个正整数n;m,保证n;m <= 10。

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

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

    输出格式:

    输出到文件chess.out 中。

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

    输入输出样例

    输入样例#1: 复制
    2 3
    2 7 3
    9 1 2
    3 7 2
    2 3 1
    输出样例#1: 复制
    2

    说明

    样例1说明:

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

    • 菲菲下在第1 行第1 列(这是第一步时唯一可以落子的格子);

    • 牛牛下在第1 行第2 列;

    • 菲菲下在第2 行第1 列;

    • 牛牛下在第1 行第3 列;

    • 菲菲下在第2 行第2 列;

    • 牛牛下在第2 行第3 列(这是这一步时唯一可以落子的格子);

    • 填满棋盘,游戏结束,盘面如下。

    菲菲的得分为:2 + 9 + 1 = 12 ;牛牛的得分为:7 + 2 + 1 = 10 。

    对于所有的测试数据,n;m <= 10 , $A_{i,j}$ ; $B_{i,j}$ <= 100000。

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。