【耻辱柱】P7074 (CSP-J2020) 方格取数

41

原先以为这是道简单题来着www

但是做完这道题,感觉自己的dp更菜了

原题是这样的:

设有 $n×m$ 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。

刚开始的时候,我想着就是dp,向下和向左很常规,但是向上有点麻烦,因为有不能经过同一个点的限制,所以dp要多加一个维度记录是否经过下面的(因为从上面转移的的不能经过下面)

然后我就开写了,很快啊,就RE了
我还有点懵,调试了下,突然被自己蠢到了,上下互相依赖啊,怎么能递归呢
于是我仔细(并不)思考了一下,改成了循环转移
但结果还是不对。为什么呢?因为对一个元素的更新会引起更多元素的更新,而显然我这样做是不对的。

后来我才意识到题面一个隐含条件:不能往左走,这时候我才意识到,只有右往左的转移是独立的,进一步的,上下的转移是单调的,于是可以先转移到左侧一列,然后下到上,上到下再跑一次。

就做出来了,但是就结果来说相当丢人。