P2258 子矩阵

    • 1.4K通过
    • 4.3K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 剪枝 动态规划,动规,dp 搜索 枚举,暴力 NOIp普及组 2014 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    给出如下定义:

    1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。

    例如,下面左图中选取第 $2$ 、 $4$ 行和第 $2$ 、 $4$ 、 $5$ 列交叉位置的元素得到一个 $2 \times 3$ 的子矩阵如右图所示。

    9 3 3 3 9

    9 4 8 7 4

    1 7 4 6 6

    6 8 5 6 9

    7 4 5 6 1

    的其中一个 $2 \times 3$ 的子矩阵是

    4 7 4

    8 6 9

    1. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。

    2. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

    本题任务:给定一个 $n$ 行 $m$ 列的正整数矩阵,请你从这个矩阵中选出一个 $r$ 行 $c$ 列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

    (本题目为2014NOIP普及T4)

    输入输出格式

    输入格式:

    第一行包含用空格隔开的四个整数 $n,m,r,c$ ,意义如问题描述中所述,每两个整数之间用一个空格隔开。

    接下来的 $n$ 行,每行包含 $m$ 个用空格隔开的整数,用来表示问题描述中那个 $n$ 行 $m$ 列的矩阵。

    输出格式:

    一个整数,表示满足题目描述的子矩阵的最小分值。

    输入输出样例

    输入样例#1: 复制
    5 5 2 3
    9 3 3 3 9
    9 4 8 7 4
    1 7 4 6 6
    6 8 5 6 9
    7 4 5 6 1
    输出样例#1: 复制
    6
    输入样例#2: 复制
    7 7 3 3  
    7 7 7 6 2 10 5
    5 8 8 2 1 6 2 
    2 9 5 5 6 1 7 
    7 9 3 6 1 7 8 
    1 9 1 4 7 8 8 
    10 5 9 1 1 8 10
    1 3 1 5 4 8 6
    输出样例#2: 复制
    16

    说明

    【输入输出样例1说明】

    该矩阵中分值最小的 $2$ 行 $3$ 列的子矩阵由原矩阵的第 $4$ 行、第 $5$ 行与第 $1$ 列、第 $3$ 列、第 $4$ 列交叉位置的元素组成,为

    6 5 6

    7 5 6

    ,其分值为:

    |6−5| + |5−6| + |7−5| + |5−6| + |6−7| + |5−5| + |6−6| =6。

    【输入输出样例2说明】

    该矩阵中分值最小的3行3列的子矩阵由原矩阵的第 $4$ 行、第 $5$ 行、第 $6$ 行与第 $2$ 列、第 $6$ 列、第 $7$ 列交叉位置的元素组成,选取的分值最小的子矩阵为

    9 7 8
    9 8 8
    5 8 10

    【数据说明】

    对于 $50\%$ 的数据, $1 ≤ n ≤ 12,1 ≤ m ≤ 12$ ,矩阵中的每个元素 $1 ≤ a_{ij} ≤ 20$ ;

    对于 $100\%$ 的数据, $1 ≤ n ≤ 16,1 ≤ m ≤ 16$ ,矩阵中的每个元素 $1 ≤ a_{ij} ≤ 1,000,1 ≤ r ≤ n,1 ≤ c ≤ m$ 。

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