#BZOJ1177

BZOJ1177 [Apio2009]Oil 二维前缀和 二维前缀最值

  在一个n*m的矩阵中,每一个位置一个数字。  现在让你选出3个k*k的矩阵,它们互不相交,问最大数值和为多少。  注意:n,m<=1500  一开始总想着dp,发现不大可能。  暴搜也不行。  然后突然发现,很简单,情况总数非常的少。  只有以下6种,从3个区域中各选择一个最大的。  然后就很简单了,我们只需...