题目连接:http://acm.nyist.net/JudgeOnline/problem.php?pid=104
解题思路与难点:感觉变成了二维后不知道怎么dp(用上一次的值),于是联想到一维求最大和的问题;这道题的关键是怎么转换成一维。
再仔细一想,题目要求是矩形的一块区域最大值,那么我们就想到了穷举纵坐标所有的情况
看到了吗,假设我需要求红色矩形的值,那么我可以利用黑色矩形和本次(黄色)的值,如果黑色矩形的和是非负数,那么红色矩形的和就是黑色矩形的和加上本次(黄色)的值,否者是本次的值,而矩形是可以被压缩成一条线的,因为是矩形的缘故(这不就转换成了一维的了吗)。
大概有C(r,2)种情况,再有c列,那么一共复杂度是c*C(r,2),是不是看到这个式子就有了大体的思路了。就是在纵坐标中任意选两个点(求出这两个点之间的和,求这个问题要用到nyoj 士兵杀敌(一)的思路),就假设这个矩形的纵坐标就是这两个点了,那么只需求横坐标的连续最大值(一维最大连续值问题)。(因为是矩形,想一想性质吧)