#P2331. [SCOI2005] 最大子矩阵

    ID: 1342 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp递推2005四川各省省选前缀和

[SCOI2005] 最大子矩阵

题目描述

这里有一个 n×mn \times m 的矩阵,请你选出其中 kk 个子矩阵,使得这个 kk 个子矩阵分值之和最大。

注意:选出的 kk 个子矩阵不能相互重叠。

输入格式

第一行为 n,m,kn,m,k,接下来 nn 行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过 3276732767)。

输出格式

只有一行为 kk 个子矩阵分值之和最大为多少。

3 2 2
1 -3
2 3
-2 3

9

提示

对于 100%100 \% 的数据,1n1001 \leq n \leq 1001m21 \leq m \leq 21k101 \leq k \leq 10