![【Topcoder 10524】BrickPuzzle 【Topcoder 10524】BrickPuzzle](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Topcoder 10524
题意:给一个\(n\times m\)的棋盘,上面有一些格子是白色的,需要被一些俄罗斯方块们覆盖,俄罗斯方块有\(4\)种:
然后这些图案不能重叠或超出边界,并且每一个图案有无限个。问最少要用多少个图案来覆盖原图。
思路:由于\(m\)比较小,所以我们考虑状压\(dp\)。
考虑\(dp(x,y,mask)\)表示当前在\((x,y)\)这个位置,\(mask\)表示从\((x,y)\)开始\(m+2\)个格子是否被覆盖的状态,最少需要用的图案数量。
之所以这样是因为绿色图案是最多需要\((x+1,y+2)\)这个格子,所以\((x,y)..(x+1,y+2)\)这\(m+3\)个格子按理说都要记录,但是\((x+1,y+2)\)在\((x,y-1)\)的时候根本不会去更新,所以直接记录\((x,y)..(x+1,y+1)\)这\(m+2\)个格子就可以了。
然后考虑转移。首先考虑这\(4\)种图案所对应的\(mask\)需要更改的位置。
- \(0、1、2、3\)
- \(0、1、m+1、m+2\)
- \(0、1、m、m+1\)
- \(1、2、m、m+1\)
然后就可以更改状态到\(nmask\)了。这里其实可以预处理出每一个图案对应更改的\(mask\),加快更新速度。
还有一种可能是这个格子就不放图案,那么必须要判断\(mask\)的第\(0\)位是否已经被覆盖或者是黑色格子不用被覆盖,如果不行就不能转移。
写的时候需要特别注意细节!!!
直接这样写是会\(tle\)或\(mle\)的,所以考虑优化。
- 用滚动数组,再用哈希表来存储\(mask\)。导致的结果:\(ac,4.2e5ms\)
- 考虑\(has_{x,y}\)表示从\((x,y)\)开始\(m+2\)个格子中哪些是白色的,然后如果当前放置的那个图案覆盖到的所有的都是黑色的,那么肯定不应该去更新这个状态。导致的结果:\(2.9e5ms\)
- 更改哈希表的哈希模数,以及增加一些\(register\)优化,导致的结果:\(2.4e5ms\)
暂时做不到更好了。
所以这告诉我们一些道理:
- 哈希表永远是状压\(dp\)的好朋友
- 调参永远是卡常的好朋友
- 多想一些小小的优化(比如这个\(has\)数组)永远是拿高分的保障