BZOJ1087 (互不侵犯King)[状压DP]

发表于 | 更新于 | | 阅读次数：

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1087

状压dp经典题
f[i][j][k]保存第i行（包括第i行）之前放了j个国王，当前行用二进制表示后对应十进制数为k的方案数。count[k]表示k所对应的二进制中1的个数。
状态转移方程比较显然：f[i][j][k]=sum{f[i-1][j-count[k]][p]}；
其中k满足 (k&(k<<1))==0
其中p满足 (p&(p<<1))==0&&((p<<1)&k)==0&&(p&k)==0&&((p>>1)&k)==0
引用自sunshinezff

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
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int n,k;
ll dp[10][513][82];
int cnt[513];
int main() {
    for(int i=0;i<513;i++) {
        int tmp=i,cc=0;
        while(tmp) {
            if(tmp&1) cc++;
            tmp>>=1;
        }
        cnt[i]=cc;
    }
    int n,K;
    scanf("%d%d",&n,&K);
    int tot=(1<<n);
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<tot;j++) {
            for(int k=0;k<=K;k++) { //k starts from 0 instead of 1
                if(!(j&(j<<1)) && cnt[j]<=k) {
                    for(int l=0;l<tot;l++)
                        if(!(j&l) && !(j&(l<<1)) && !(j&(l>>1)) && !(l&(l<<1)))
                        dp[i][j][k]+=dp[i-1][l][k-cnt[j]];
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<tot;i++) {
        ans+=dp[n][i][K];
    }
    //printf("%I64d",ans);
    printf("%lld",ans); // you cannot use %I64d in BZOJ
}