Problem6191--NOI2013湖北省选 二试 第3题 切糕

6191: NOI2013湖北省选 二试 第3题 切糕

[Creator : ]
Time Limit : 5.000 sec  Memory Limit : 512 MB

Description

经过千辛万苦小A 得到了一块切糕,切糕的形状是长方体,小A 打算拦腰将切糕切成两
半分给小B。出于美观考虑,小A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮
她找出最好的切割方案。
出于简便考虑,我们将切糕视作一个长P、宽Q、高R 的长方体点阵。我们将位于第z
层中第x 行、第y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z),它有一个非负的不
和谐值v(x,y,z)。一个合法的切面满足以下两个条件:
1. 与每个纵轴(一共有P*Q 个纵轴)有且仅有一个交点。即切面是一个函数f(x,y),对
于所有1≤x≤P, 1≤y≤Q,我们需指定一个切割点f(x,y),且1≤f(x,y)≤R。
2. 切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。对于所有
的1≤x,x’≤P 和1≤y,y’ ≤Q,若|x-x’|+|y-y’|=1,则|f(x,y)-f(x’,y’)| ≤D,
其中D 是给定的一个非负整数。
可能有许多切面f 满足上面的条件,小A 希望找出总的切割点上的不和谐值最小的那个,
最小。

Input

第一行是三个正整数P,Q,R,表示切糕的长P、
宽Q、高R。第二行有一个非负整数D,表示光滑性要求。接下来是R个P行Q列的矩阵,第z个
矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。
100%的数据满足P,Q,R≤40,0≤D≤R,且给出的所有的不和谐值不超过1000。

Output

仅包含一个整数,表示在合法基础上最小的总不和谐值。


【输入输出样例】
input         output
2 2 2         6
1
6 1
6 1
2 6
2 6
input         output
2 2 2         12
0
5 1
5 1
2 5
2 5
【样例解释】
第一组样例中最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1。
第二组样例中最佳切面的f为f(1,1)=f(2,1)=f(1,2)=f(2,2)=1。

Sample Input Copy

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output Copy

6

Source/Category