P2295 MICE 网格中的DP

P2295 MICE 网格中的DP


P2295 MICE 网格中的DP

分析

很好的一道网格中的\(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]); \]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wppxps.html