tkdsheep-solution-0044

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

其实这题是相当简单的，可能比赛的时候大家都没有正确估算是有效的状态数，怕超时不敢写吧
首先计算出每一行可能的状态数（只考虑水果横着攻击不会互相打到），每一行的状态最多是2的12次方，但由于攻击范围相互限制，实际的有效状态数只有几百吧
然后就是按每两行来dp，dp[r][i][j]表示前r行，第r-1行的状态为i，第r行的状态为j，答案是多少
可以用类似滚动数组的做法节省空间，然后把（i,j)作为一个pair塞到map里来dp就很好写了
状态转移的时候只需判断2种情况，假设前两行状态分别为x和y，当前更新的这一行的状态为z，则首先z和y不能有水果竖直攻击到，这个直接用&就能判断
然后z和y不能斜着打到，可以将y左移、右移后再与z做&
然后就是判断x和z不能斜着攻击到，这个只需在判断时额外检查一下y所在的行有没有石头挡住水果的攻击即可

其实这题是相当简单的，可能比赛的时候大家都没有正确估算是有效的状态数，怕超时不敢写吧

首先计算出每一行可能的状态数（只考虑水果横着攻击不会互相打到），每一行的状态最多是2的12次方，但由于攻击范围相互限制，实际的有效状态数只有几百吧

然后就是按每两行来dp，dp[r][i][j]表示前r行，第r-1行的状态为i，第r行的状态为j，答案是多少

可以用类似滚动数组的做法节省空间，然后把（i,j)作为一个pair塞到map里来dp就很好写了

状态转移的时候只需判断2种情况，假设前两行状态分别为x和y，当前更新的这一行的状态为z，则首先z和y不能有水果竖直攻击到，这个直接用&就能判断

然后z和y不能斜着打到，可以将y左移、右移后再与z做&

然后就是判断x和z不能斜着攻击到，这个只需在判断时额外检查一下y所在的行有没有石头挡住水果的攻击即可