【SCOI2005】【BZOJ1087】互不侵犯King（狀壓dp）

在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

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小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。