怎么换主题~是主题,不是皮肤!
603
2022-05-29
在N×N的棋盘里面放K个国王
每个国王会攻击它周围的一圈共8个格子
使他们互不攻击,共有多少种摆放方案
N <= 9
用01串表示某一行放置的情况
首先枚举当前做到第几行,以及当前一共放了几颗棋子。
于是状态f[i][j][k]表示到第i行,一共放j个棋子(包括这之前的),且第i行的状态是k的方案数。
再考虑转移。这一行肯定是由上一行的状态转移过来的,那么我们可以再枚举上一行的状态。
很自然的,发现这会超时。每次枚举一种状态就需要2^9,两重循环已经快爆掉了!我们可以发现一件事情。比如n=5,我们每次枚举到的11111,11011,10111,01011这些状态都是无效的。那么我们可以先预处理一下对于每一行的所有可行的状态(就是不能有连续的1)。
这样的效率仍然不高——我们还可以对于每种可行的状态i,j,预处理i和j是否能够相邻,这样我们在DP的时候,就可以O(1)来转移了。(这里也可以不预处理,每次直接判断ij能否相邻也可。)
最后,记得开long long。
#include 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。