#P1184. [HNOI2007]海盗分宝[废题]

[HNOI2007]海盗分宝[废题]

[HNOI2007] 海盗分宝(本站恢复版本)

题目描述

共有l行、w列土陶盒,每个盒子有非负价值。输入从最上面一行到最下面一行给出;在描述海盗前进方向时,把最下面一行编号为1。海盗向上行走,可以选择至多h批,每批选取n行、m列的连续矩形,并把其价值全部收入木箱。长为m的一边沿水平的w列方向,n沿竖向的l行方向。

设第k批的左下角在第i_k行、第j_k列。首先矩形必须完全在棋盘内:

1≤ik≤l−n+1,1≤jk≤w−m+1.1\le i_k\le l-n+1,\qquad 1\le j_k\le w-m+1.

本站恢复版本采用存档实现中明确的横向条件:

$$\left\lfloor\frac{|m+2j_k-w|}{2}\right\rfloor\le a.$$

各批按海盗前进方向排序。当相邻两批的起始列相同,要求 ik−ik−1≥d1i_k-i_{k-1}\ge d_1;起始列不同,则要求 ik−ik−1≥d2i_k-i_{k-1}\ge d_2。第一批没有与前一批之间的距离限制。

求至多h批能获得的最大总价值。保证d_1、d_2都不小于n,因此各批纵向不重叠,已经取走后补回的空盒不影响计数。

输入格式

第一行八个正整数l,w,m,n,h,a,d_1,d_2。随后l行,每行w个整数,按从上到下、从左到右输入价值。

1≤l,w,a,d1,d2≤20001\le l,w,a,d_1,d_2\le2000,1≤m,n≤2001\le m,n\le200,1≤h≤201\le h\le20,d1,d2≥nd_1,d_2\ge n;每格价值在0到255之间。若矩形无法放入棋盘,则答案为0。

输出格式

一个整数,最大总价值。

样例

10 12 3 2 3 5 2 3
0 0 0 1 0 1 1 1 9 1 1 1
1 1 2 1 1 1 0 0 8 2 1 8
1 0 1 0 1 6 1 1 0 0 1 1
1 1 2 1 2 1 1 1 3 1 1 1
0 1 0 1 1 1 2 1 6 0 2 1
1 1 0 1 0 1 1 2 1 1 1 0
1 0 1 1 1 0 1 0 1 1 0 1
1 1 0 1 1 1 9 0 0 1 1 1
0 0 1 0 1 2 1 9 1 1 0 1
0 1 1 1 1 1 9 1 1 1 1 1
59

恢复说明

原存档正文的行列定义相反,横向条件还丢失了对称性和半格取整约定。本恢复版本根据原图(l竖向、w横向、m水平、n竖向)和存档参考实现明确采用以上完整数学规则;它是本站明确修订的版本,不宣称找回了原官方文字的唯一原意。原10组测试保留并用于核验。