1820 问题 F: 蓝桥杯2014年第五届真题-殖民地

  

带着殖民扩张的野心，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列右方的围栏建立代价。

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

零基础同学可以先学习视频课程，包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程，提供视频讲解以及配套习题，还有老师答疑，点击这里了解课程详情