BZOJ2719 - [Violet 4]银河之星

BZOJ2719 - Click Here

  

Description

  

Input

  

Output

  

Solutions

  这题是昨天NOIP模拟赛的压轴题。原本能切掉的,但是对于状态数有点虚,不敢上记忆化,然后就GG了。

  

  对于一个棋子而言,在没有吃棋子的状况下,它只能移动3格。

  因此可以将这$N \times M$的网格分成

  1 2 3

  4 5 6

  7 8 9

  共9个格子,网格内所有格子都可以从9个格子的其中一个格子到达。

  这样子,就将$N \times M$压缩成了一个$3 \times 3$的方格。

  

  接着再来考虑一下吃棋子的情况。

  将吃棋子放到这$3 \times 3$方格上来分析,不难看出,其实吃棋子等价于将两个棋子合并成一个棋子。而且这三个棋子必定是在同一行、列或对角线

  如果把这个$3 \times 3$的格子看做一个状态的话,很容易可以转移,而且由于每次合并后,棋子都会减少,因此又保证了无后效性,直接记忆化搜索即可。

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang