ABC358G AtCoder Tour 题解

思路

思路是简单的，使用分层图的思想递推地求出对于每个格子走了 $k\leq n\times m$ 步之后最大的价值（记为 $val_{x,y,k}$ ，递推式为 $val_{x,y,k}=\max\{val_{x',y',k-1}+a_{x,y}\},|x'-x|+|y'-y|\leq 1$ ），记 $mk=\min(k,n\times m)$ ，最后答案则是 $\max\{val_{x,y,mk}+a_{x,y}\times (k-mk)\}$ ，时间复杂度 $\mathcal{O}(n^2m^2)$ 。

这里证明一下“至多走 $n\times m$ 步之后就会停留在一个格子里这个结论”。

考虑反证法，假设用上文的方法求出来的答案为 $ans_0$ ，最后停在 $a_{x,y}$ 。有一条路径 $p$ 已经把所有 $n\times m$ 个格子都走过一遍了，却还在继续移动，没有停在一个格子里，最后得到的价值为 $ans_1$ ，且 $ans_1>ans_0$ 。

沿用上文的定义，则 $ans_1-\sum{a}>ans_0-\sum{a}$ 即 $ans_1-\sum{a}>a_{x,y}\times (k-mk)$ 。

这意味着 $p$ 经过的之后的格子里的价值总和的平均值一定高于 $a_{x,y}$ ，也就是一定 $\exist a_{x',y'}\in p,a_{x',y'}>a_{x,y}$ ；那么把所有格子走一遍然后停在 $a_{x',y'}$ 最后得到的价值一定高于原来的 $ans_0$ ，与一开始 $ans_0$ 为最优解的条件矛盾，于是结论得证。