如果在赛场上告诉我,这道题就是暴力的记忆化搜索,我肯定就搞了

如果在赛场上告诉我,线段树lazy标记是可以过的,我肯定现场就学了就过了

哎,还是实力不够,校赛给我了一发补题的机会也挺好的


题意:n*m的矩阵,每个点上有权值,一个人从左上角到右下角遍历两次,若两条路径有重复点,则只计算一次,求最大的收益,n和m的最大范围100


看到这种题,我知道是DP

正常情况的设置是:dp【i】【j】【k】【l】为第一个人走到了【i】【j】这个点,第二个走到【k】【l】,所能够得到的最大价值

但是范围在100,这样开数组是爆炸的,能不能少一维


注意到题意:只能从左上角走到右下角,意味着总步数是固定的:n+m-2

所以可以用总步数和两个人在x方向的步数,来计算y方向的步数从而减少一维变量

即定义为:dp【step】【x1】【x2】为当前总共走了step步,第一个人的坐标是【x1】【step-x1】,第二个人的坐标是【x2】【step-x2】所能得到的最大价值


因此,剩下的方向:怎么得到最大价值:记忆化搜索

两个人最多四种方向,依次判断就好:AB下;AB右;A下B右;A右B下


剩下的代码就好写了,初始化为-1,然后dfs记忆化搜索,只需要判断4种方向能不能走(有没有点在边界上判断一发即可)

还是太弱,贴上我谷巨的博客压压惊

膜拜我谷


另外呢,这个题如果把2次,改成3次,甚至更多的K次,用dp就不方便了

就需要用最小费用最大流模板处理最大费用最大流问题,暂时还不会,留个坑在这吧