题解 LuoGu P1896 互不侵犯King

作者: MayFlyyh 分类: DP 发布时间: 2018-03-17 21:12 ė 6 没有评论

LuoGu P1896 互不侵犯King

题目描述

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

输入格式:
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

输出格式:
所得的方案数


对于每个格子有两种状态,一种是放一种是不放,其中这个点放了,左右上下对角线都不能放

对于第i行第X格放了,第i-1行自然不能放,如果i-1行放了,i行自然不能放

所以我们只用知道上面放了没放,而不用管下面(传递性)

根据数据范围,我们用二进制串表示一行的状态,每行最多有9列 就最多有2^9^状态

从0——2^9^,我们再预处理出每种状态对应放了几个国王

num[i]=num[i>>1]+(i&1)

i表示状态,num[i]表示i状态对应的国王数(DFS也可以)

分析一下我们需要这几个信息:

1.一个现在处理到了第i行

2.一个是第i行的每个格子的状态(注意是第i行)

3.一个是现在一共放了几个King(注意是一共而不是此行)

所以我们设置DP[i][j][k]表示第i行状态j放了k个国王

由于国王左右不能再放国王

举个例子:

原本 00110

左移 01100

右移 00011

有上述栗子可知,如果有国王左边和右边有国王,

将向左移和向右移的结果分别对原串进行and操作

如果得到的结果不为0即不合法

枚举上一行的状态,并且通过刚才的判断方法判断上一行原串,左移1格,右移一格后的结果分别与当前行状态and操作,

如果得到结果不为0说明当前行和上一行状态冲突

所以我们要枚举当前是第i行,当前行状态,上一行状态,当前放了k个

注意要预处理一下第一行的值,第一行任何合法情况都设置为1

最后还要统计方案个数

代码:

#include<bits/stdc++.h>
int n,k;
long long dp[100][100][2000];
long long num[20000];
long long ans=0;
long long max;
int main (){
    scanf("%d %d",&n,&k);
    int NN=(1<<(n))-1;
    for(int i=1;i<=NN;++i){
        num[i]=num[i>>1]+(i&1);
    }
    for(int i=0;i<=NN;++i)
        dp[1][num[i]][i]=1;

    for(int i=2;i<=n;++i){
        for(int j=0;j<=k;++j){
            for(int l=0;l<=NN;++l){
                if(((l<<1)&l)) continue;
                if(((l>>1)&l)) continue;
                for(int r=0;r<=NN;++r){
                    if(((r<<1)&r)) continue;
                    if(((r>>1)&r)) continue;
                    if(r&l) continue;
                    if((r>>1)&l) continue;
                    if((r<<1)&l) continue;
                    if(j-num[l]<0) continue;
                    dp[i][j][l]+=dp[i-1][j-num[l]][r];
                }
            }
        }
    }
    for(int i=0;i<=NN;++i){
        ans+=dp[n][k][i];
    }

    printf("%lld",ans);
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/173

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部