2013安徽省奥林匹克信息学试题(小学组)第三题解答

我们使用map[i][j]来记录每个单元格中的糖果数量。对于被老鼠咬过的单元格，我们把这个单元格中的糖果数改成一个很小的负数(比如，-10000000)，这样问题就变成了求一个和以及最大的子矩阵。

预处理数组f[i][j]以表示map[1][j]+map[2][j]+map[3][j]+...映射[i] [j]。

对F数组进行预处理后，我们就可以很容易地求出K列从I行到J行所有糖果数的和。

(即f[j][k]-f[i-1][k])

这样我们就枚举出上边界I和下边界J，用上边界I和下边界J找到最大的子矩阵来更新答案。

定义数组b[k]=f[j][k]-f[i-1][k]

问题变成求一个区间l~r使b[l]+b[l+1]+...b[r]最大值。

重定义c[i]=b[1]+b[2]+...b[i]

那么l~r的和可以表示为c[r]-c[l-1]。

那么对于每一个确定的上下限，我们来枚举R记录1~r-1中最小的C，并从c[r]中减去它来更新答案。

你可以试着自己写代码，如果真的需要可以问我。