BZOJ 1087: [SCOI2005]互不侵犯King [状压DP]

2022-10-25 09:23:54

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3336 Solved: 1936
[Submit][Status][Discuss]

Description

　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

　　只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

　　方案数。

Sample Input

3 2

Sample Output

orz popoqqq

状压DP，将每一行的方案二进制压成一维，令f[i][j][k]为第i行用去j个国王状态为k的方案数，然后状态转移如下：

f[i][j][k]=Σf[i-1][j-d[k]][l]

其中l&k=0,l>>1&k=0,l<<1&k=0,d[k]为k的二进制中1的个数

暴力转移即可

记得开long long

预处理来优化

需要判断自身状态可行，判断可行用了移位很巧妙！

//

//  main.cpp

//  bzoj1087

//

//  Created by Candy on 2016/12/24.

//  Copyright © 2016年 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N=,M=;

int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,s;

int g[M][M],can[M],d[M];

ll f[N][N*N][M];

inline int digit(int x){

    int re=;

    while(x) re+=x&,x>>=;

    return re;

}

inline bool check(int x){return !(x<<&x||x>>&x);}

inline bool check(int x,int y){

    return !(x&y||x<<&y||x>>&y);

}

int main(int argc, const char * argv[]) {

    n=read();m=read();s=<<n;

    for(int i=;i<s;i++){

        for(int j=i;j<s;j++)g[i][j]=g[j][i]=check(i,j);

        d[i]=digit(i);

        can[i]=check(i);

    }

    f[][][]=;

    for(int i=;i<=n;i++){

        int t=min(m,i*n/+);

        for(int j=;j<=t;j++)

            for(int k=;k<s;k++) if(can[k]&&d[k]<=j)

                for(int l=;l<s;l++) if(can[l]&&g[k][l]&&d[k]+d[l]<=j)

                    f[i][j][k]+=f[i-][j-d[k]][l];

    }

    ll ans=;

    for(int i=;i<s;i++) ans+=f[n][m][i];

    printf("%lld\n",ans);

    return ;

}

码农公寓