洛谷P1896/SCOI2005 互不侵犯

@Pelom  September 26, 2019

题意:

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

数据范围: $ 1 \le N \le 9,0 \le K \le N * N $

题解:

算法:状压dp

使用 $stt[]$ 记录每一种状态,二进制下从低位到高位记录此行从左到右是否放置国王。

并且由于有数量限制,使用 $sum[]$ 记录该种状态使用的国王数。

考虑状态转移方程,预处理出每一种状态 $stt[]$ 及其使用的国王数 $sum[]$ ,用 $dp[i][j][s]$ 表示考虑前 $i$ 行且第 $i$ 行状态编号为 $j$ ,前 $i$ 行共使用 $s$ 个国王时的方案数。可以得出:

$$dp[i][j][s]= \sum dp[i-1][k][s-sum[j]]$$

其中 $j$ 与 $k$ 对应的状态需满足题目条件,即不能为以下几种情况:

sum[j]&sum[k](上/下)

(sum[j]<<1)&sum[k](左上/右下)

sum[j]&(sum[k]<<1)(右上/左下)

此外,注意开 $long\ long$。

代码:

#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int N=15;
int n,m;
int tot,cnt;
LL ans;
int sum[1<<N],stt[1<<N];
LL dp[N][1<<N][N*N];
inline int calc(int x){
    int res=0;
    for(;x;x&=x-1)
        res++;
    return sum[cnt]=res;
}
int main(){
    scanf("%d%d",&n,&m);
    tot=(1<<n)-1;
    for(int i=0;i<=tot;i++)
        if(!(i&(i<<1))){
            stt[++cnt]=i;
            dp[1][cnt][calc(i)]=1;
        }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=cnt;j++){
            int x=stt[j];
            for(int k=1;k<=cnt;k++){
                int y=stt[k];
                if((x&y) || (x&(y<<1)) || ((x<<1)&y))
                    continue;
                for(int l=0;l<=m;l++)
                    dp[i][j][sum[j]+l]+=dp[i-1][k][l];
            }
        }
    for(int i=1;i<=cnt;i++)
        ans+=dp[n][i][m];
    printf("%lld",ans);
    return 0;
}

添加新评论