#P594. 【HAOI2007】 修筑绿化带

    ID: 594 传统题 1000ms 256MiB 尝试: 2 已通过: 0 难度: 10 上传者: 标签>动态规划数据结构单调队列递推递推HAOI2007

【HAOI2007】 修筑绿化带

【问题描述】

为了增添公园的景致,现在需要在公园中修筑一个花坛,同时在画坛四周修建一片绿化带,让花坛被绿化带围起来。

如果把公园看成一个MxN的矩形,那么花坛可以看成一个CxD的矩形,绿化带和花坛一起可以看成一个AxB的矩形。如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和,那么,

绿化带的肥沃度=AxB块的肥沃度-CxD块的肥沃度

为了使得绿化带的生长得旺盛,我们希望绿化带的肥沃度最大。

【输入格式】

第一行有6个正整数M,N,A,B,C,D。

接下来一个M*N的数字矩阵,其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。

【输出格式】

一个正整数,表示绿化带的最大肥沃程度。

【输入样例】

4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

【输出样例】

132

【数据范围】

30%的数据,1<=M,N<=50。

100%的数据,1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2,1<=“肥沃度”<=100。