lightoj 1071 DP/网络流

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

如果在赛场上告诉我，线段树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就不方便了

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