CF1840F
原题
翻译
首先先说一个我想的错误的做法
因为从\((0,0) \rightarrow (i,j)\)肯定是时间越短越好，因为如果时间长了不妨在\((i,j)\)等一会，这样答案肯定不劣于走的慢的
于是直接设\(dp_{i,j}\)表示从\((0,0) \rightarrow (i,j)\)的最短时间
然后你就被骗到了
因为第一句话的显然是完全错误的，因为你只能向右和向下走，假如你当前在\((i,j)\)想走到\((i,j + 1)\)，但这时突然在第\(i\)行放炮，你就会发现你无路可走，只能受到炮击
下面开始说正解：
先考虑一个比较暴力的状态：\(dp_{i,j,t}\)表示从\((0,0) \rightarrow (i,j)\)，在\((i,j)\)时时间为\(t\)是否可行
容易得到递推式：
\[dp_{i,j,t} = dp_{i-1,j,t-1} | dp_{i,j-1,t-1} | dp_{i,j,t-1}
\]
但这个做法时间和空间复杂度都为\(O(n^2m^2)\)，是很难卡过去的
于是我们考虑优化一下状态，我们容易发现\(i+j \leq t \leq i+j+r\)
所以我们可以设\(dp_{i,j,t}\)表示从\((0,0) \rightarrow (i,j)\)，在\((i,j)\)时时间为\(i+j+t\)是否可行
容易得到递推式：
\[dp_{i,j,t} = dp_{i-1,j,t} | dp_{i,j-1,t} | dp_{i,j,t}
\]
最终复杂度\(O(nmr)\)