分析
很好的一道网格中的\(DP\)题
我们设\(f[x][y]\)为小象到达坐标为\((x,y)\)的点时看到的最少的老鼠的数量
但是这样定义是不好转移的,因为小象可能从上面的格子转移下来,也可能从上面的格子转移过来
所以我们用三维数组记录状态,我们设\(f[x][y][0]\)为当前格子从正上方的格子转移过来所看到的最少的老鼠的数量
\(f[x][y][1]\)为当前格子从正左方的格子转移过来所看到的最少的老鼠的数量
我们来分情况讨论一下
无非是考虑当前的位置和当前上下左右的\(4\)个格子,去一下重
1、当前格子从正上方转移过来,当前格子正上方的格子也由正上方的格子转移过来
此时当前格子的价值\(a[i][j]\)已经在\(f[i-1][j][0]\)中计算过
而当前格子正上方的格子的价值\(a[i-1][j]\)已经在\(f[i-2][j][0]\)或\(f[i-2][j][1]\)中计算过
\[f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+a[i][j-1]+a[i][j+1]+a[i+1][j]); \]