#P3087. Coci2009 misolovke

    ID: 2242 传统题 1000ms 512MiB 尝试: 26 已通过: 15 难度: 7 上传者: 标签>CF2200提高线性 DP状压 DP单调队列优化 DP前后缀最值一维前缀和滚动数组高精度加法

Coci2009 misolovke

题目描述

给定一个 n×nn\times n 的网格。

每个格子里至少会有一个捕鼠器,并且已知每个格子里的捕鼠器个数。现在需要在每一行中选取恰好 kk 个连续的格子,把里面的捕鼠器全部拿走,并且需要满足老鼠不能从网格最左边到网格最右边也不能从网格最上面到网格最下面。

老鼠行走的方向是上下左右四个方向,且只能经过没有捕鼠器的格子。

求拿走捕鼠器个数的最大值。

输入格式

第 11 行 22 个整数 n,kn,k。

第 22 到 n+1n+1 行,每行 nn 个整数。表示网格中每个格子里的捕鼠器个数。

输出格式

仅一个整数,表示拿走捕鼠器个数的最大值。

4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1
36

数据规模与约定

对于 100%100\% 的数据,2≤n≤2502\le n\le 250,1≤k≤n21\le k\le\frac{n}{2}。