网站首页
编程语言
数据库
系统相关
其他分享
编程问答
joisc2007
2024-11-21
【题解】AT_joisc2007_mall ショッピングモール (Mall)
原题传送门温馨提示:岛国题要换行!需要求一个矩阵的和,考虑二维前缀和。题目中不允许矩阵中有负数,结合求和的最小值,我们把负数赋为最大值不就行了吗。接下来就是求二维前缀和了。基于容斥原理,二维前缀和有如下递推关系:\[sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+c_{i