#P2258. [NOIP2014 普及组] 子矩阵

    ID: 1272 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp搜索2014NOIp 普及组枚举暴力剪枝

[NOIP2014 普及组] 子矩阵

题目背景

NOIP2014 普及组 T4

题目描述

给出如下定义:

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

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

99 3\color{#6a5acd}3 33 3\color{#6a5acd}3 9\color{#6a5acd}9
9\color{#6a5acd}9 4\color{blue}4 8\color{#6a5acd}8 7\color{blue}7 4\color{blue}4
11 7\color{#6a5acd}7 44 6\color{#6a5acd}6
6\color{#6a5acd}6 8\color{blue}8 5\color{#6a5acd}5 6\color{blue}6 9\color{blue}9
77 4\color{#6a5acd}4 55 6\color{#6a5acd}6 1\color{#6a5acd}1

此矩阵的其中一个 2×32\times3 的子矩阵是:

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

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

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

输入格式

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

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

输出格式

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

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
6
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
16

提示

样例 1 说明

该矩阵中分值最小的 2233 列的子矩阵由原矩阵的第 44 行、第 55 行与第 11 列、第 33 列、第 44 列交叉位置的元素组成,为:

66 55 66
77 55 66

其分值为 65+56+75+56+67+55+66=6|6-5|+|5-6|+|7-5|+|5-6|+|6-7|+|5-5|+|6-6|=6

样例 2 说明

该矩阵中分值最小的 3333 列的子矩阵由原矩阵的第 44 行、第 55 行、第 66 行与第 22 列、第 66 列、第 77 列交叉位置的元素组成,选取的分值最小的子矩阵为:

99 77 88
99 88 88
55 1010

数据范围

  • 对于 50%50\% 的数据,1n121\leq n\leq 121m121\leq m\leq 12,矩阵中的每个元素 1ai,j201\leq a_{i,j}\leq20

  • 对于 100%100\% 的数据,1n161\leq n\leq 161m161\leq m\leq 16,矩阵中的每个元素 1ai,j10001\leq a_{i,j}\leq 10001rn1\leq r\leq n1cm1\leq c\leq m