P2258 子矩阵

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

题解

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

    推荐的相关题目 显示

    题目描述

    给出如下定义:

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

    例如,下面左图中选取第2、4行和第2、4、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

    的其中一个2*3的子矩阵是

    4 7 4

    8 6 9

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

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

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

    (本题目为2014NOIP普及T4)

    输入输出格式

    输入格式:

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

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

    输出格式:

    输出共1行,包含1个整数,表示满足题目描述的子矩阵的最小分值。

    输入输出样例

    输入样例#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[i][j] ≤ 20;

    对于100%的数据,1 ≤ n ≤ 16,1 ≤ m ≤ 16,矩阵中的每个元素1 ≤ a[i][j] ≤ 1,000,

    1 ≤ r ≤ n,1 ≤ c ≤ m。

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