#P1184. [HNOI2007]海盗分宝[废题]
[HNOI2007]海盗分宝[废题]
[HNOI2007] 海盗分宝(本站恢复版本)
题目描述
共有l行、w列土陶盒,每个盒子有非负价值。输入从最上面一行到最下面一行给出;在描述海盗前进方向时,把最下面一行编号为1。海盗向上行走,可以选择至多h批,每批选取n行、m列的连续矩形,并把其价值全部收入木箱。长为m的一边沿水平的w列方向,n沿竖向的l行方向。
设第k批的左下角在第i_k行、第j_k列。首先矩形必须完全在棋盘内:
本站恢复版本采用存档实现中明确的横向条件:
$$\left\lfloor\frac{|m+2j_k-w|}{2}\right\rfloor\le a.$$各批按海盗前进方向排序。当相邻两批的起始列相同,要求 ;起始列不同,则要求 。第一批没有与前一批之间的距离限制。
求至多h批能获得的最大总价值。保证d_1、d_2都不小于n,因此各批纵向不重叠,已经取走后补回的空盒不影响计数。
输入格式
第一行八个正整数l,w,m,n,h,a,d_1,d_2。随后l行,每行w个整数,按从上到下、从左到右输入价值。
,,,;每格价值在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组测试保留并用于核验。