给出一个地图,每个点上有相应数量的cheese,从(0,0)开始,每到一个格子就把这个格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子数为k,每一步之后的一格所包含的cheese数量要比之前一格多…怎样才能使得所得的cheese数最多呢,输出最多的cheese数.
刚开始我想的搜索,但是无门.但是看题之前已经知道是dp了,就一直往那方面想,一开始就想到了从cheese最大点开始,把他相应范围内的最大数更新一下,也就是dp[i][j] = map[i][j] + (与i,j在合法范围内dp[*][*]最大值),dp[i][j]表示从(i,j)开始所能得到的最多cheese。但是想想实现起来比较麻烦。昨天晚上睡觉上微博的时候，突然想到把这些点按照cheese数排列，然后从前往后进行dp，相当于LIS，只不过中间的限制条件比较多。按照这个思路，我写出代码，并且ac掉：
（更多…）