Dotcpp  >  编程题库  >  蓝桥杯2014年第五届真题-殖民地
题目 1820:

蓝桥杯2014年第五届真题-殖民地

时间限制: 1Sec 内存限制: 128MB 提交: 19 解决: 0

题目描述

  

带着殖民扩张的野心,Pear和他的星际舰队登上X星球的某平原。为了评估这块土地的潜在价值,Pear把它划分成了M*N格,每个格子上用一个整数(可正可负)表示它的价值。


    Pear要做的事很简单——选择一些格子,占领这些土地,通过建立围栏把它们和其它土地隔开。对于M*N的格子,一共有(M+1)*N+M*(N+1)条围栏,即每个格子都有上下左右四个围栏;不在边界上的围栏被相邻的两个格子公用。大概如下图【p1.png】所示。

    图中,蓝色的一段是围栏,属于格子1和2;红色的一段是围栏,属于格子3和4。
    
    每个格子有一个可正可负的收益,而建围栏的代价则一定是正的。

    你需要选择一些格子,然后选择一些围栏把它们围起来,使得所有选择的格子和所有没被选的格子严格的被隔开。选择的格子可以不连通,也可以有“洞”,即一个连通块中间有一些格子没选。注意,若中间有“洞”,那么根据定义,“洞”和连通块也必须被隔开。

    Pear的目标很明确,花最小的代价,获得最大的收益。

输入格式

输入第一行两个正整数M N,表示行数和列数。
接下来M行,每行N个整数,构成矩阵A,A[i,j]表示第i行第j列格子的价值。
接下来M+1行,每行N个整数,构成矩阵B,B[i,j]表示第i行第j列上方的围栏建立代价。
特别的,B[M+1,j]表示第M行第j列下方的围栏建立代价。
接下来M行,每行N+1个整数,构成矩阵C,C[i,j]表示第i行第j列左方的围栏建立代价。
特别的,C[i,N+1]表示第i行第N列右方的围栏建立代价。

输出格式

一行。只有一个正整数,表示最大收益。

样例输入

3 3
65 -6 -11
15 65 32
-8 5 66
4 1 6
7 3 11
23 21 22
5 25 22
26 1 1 13
16 3 3 4
6 3 1 2

样例输出

123

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签

通过率

统 计

 提交 19
 正确 0
 格式错误 0
 答案错误 4
 时间超限 6
 内存超限 0
 输出超限 2
 运行错误 7
 编译错误 0