【SCOI2005】【BZOJ1087】互不侵犯King(状压dp)

网友投稿 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 using namespace std; const int maxn = 512; typedef long long LL; int c1[maxn], cnt[maxn], c2[maxn][maxn]; LL ans, f[10][100][maxn]; int main(){ int n, m; cin>>n>>m; int all = (1<>1))==0){ c1[i] = 1; for(int x = i; x; x >>= 1) cnt[i]+= (x&1); } } for(int i = 0; i <= all; i++)if(c1[i])f[1][cnt[i]][i] = 1; for(int i = 1; i < n; i++){ for(int j = 0; j <= all; j++)if(c1[j]){ for(int k = 0; k <= all; k++)if(c1[k]){ if(((j&k)==0)&&((j&(k>>1))==0)&&((j&(k<<1))==0)){ for(int p = cnt[j]; p+cnt[k]<=m; p++) f[i+1][p+cnt[k]][k] += f[i][p][j]; } } } } for(int i = 0; i <= all; i++)ans += f[n][m][i]; cout<

1

2

3

【SCOI2005】【BZOJ1087】互不侵犯King(状压dp)

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小时内删除侵权内容。

上一篇:【管理】企业项目的OKR实战
下一篇:Spring Boot + Security + MyBatis + Thymeleaf + Activiti 快速开发平台
相关文章