美文网首页动态规划动态规划
题解 [SCOI2005] 互不侵犯King (状压DP)

题解 [SCOI2005] 互不侵犯King (状压DP)

作者: Ricardo_Y_Li | 来源:发表于2017-10-23 17:23 被阅读0次
Chtholly Nota Seniorious

题目描述

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

输入输出格式

输入格式
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
输出格式
所得的方案数

输入输出样例

输入样例#1

3 2

输出样例#1

16

解题思路

很典型的一道状态压缩DP的题,我们只需要枚举N行中每一行的状态即可,如果此行的状态与上一行的状态不相冲突即可转移
故我们维护的状态变量即为f[ i ][ j ][ k ]表示在第 i 行放了 j 个国王,此时这一行的状态为 k (k 中 1 表示放, 0 表示不放)此时的方案数
那么我们在状态转移时只需要把上一行可能的状态能够得到的方案数加起来即可
以下是C++代码,详细细节看注释

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
ll n,cnt,k;//cnt为一行中最大状态
ll f[15][110][1<<9],c[1<<9],ans=0;//c[i]表示在i状态下的国王数

inline ll read(){//快读不解释
    ll Forca=0,Barca=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-')
            Barca=-1;
        c=getchar();
    }
    while(c<='9' && c>='0'){
        Forca=Forca*10+(ll)(c-'0');
        c=getchar();
    }
    return Forca*Barca;
}

inline bool check(ll x,ll y){//判断两种状态是否冲突
    if((x&y)!=0) return 0;//状态x与状态y之间有位置相同的国王,冲突
    if((x&(x<<1))>0) return 0;//状态x本身有相邻国王,冲突
    if((y&(y<<1))>0) return 0;//状态y本身有相邻国王,冲突
    if((x&(y<<1))>0) return 0;//状态x中有国王在状态y中国王的左下,冲突
    if((y&(x<<1))>0) return 0;//状态y中有国王在状态x中国王的右下,冲突
    return 1;//不符合一切冲突条件,即不冲突
}

int main(){
    n=read(),k=read();
    cnt=(1<<n)-1;//处理出最大状态,即为2^n-1
    for(int i=1;i<=cnt;i++)
        c[i]=c[i>>1]+(i&1);//预处理c,位运算加速
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=cnt;j++)//j为本行状态
            for(int t=0;t<=cnt;t++)//t为上一行状态
                if(check(j,t)){//两个状态不相冲突即可转移
                    for(int cc=c[j]+c[t];cc<=k;cc++)//枚举可能放的国王数
                        f[i][cc][j]=f[i][cc][j]+f[i-1][cc-c[j]][t];
                }
    for(int i=0;i<=cnt;i++)
        ans+=f[n][k][i];
        //把总共n行中共放了k个国王时所有可能的状态能够取到的方案加和即为答案
    cout<<ans<<endl;
    return 0;
}

相关文章

  • 题解 [SCOI2005] 互不侵犯King (状压DP)

    题目描述 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右...

  • BZOJ-1087: [SCOI2005]互不侵犯King(状压

    题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1087 先...

  • 状压DP

    最短Hamilton路径 原题链接[https://www.acwing.com/activity/content...

  • DP训练——状压DP

    状压DP BZOJ1087题意在的棋盘里面放个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以...

  • 状压DP系列

    几点注意: 1.数组下标从1开始比较方便 zoj Easy 2048 Again保存状态的时候是保存下降子序列的情...

  • LeetCode 状压dp

    5639. 完成所有工作的最短时间[https://leetcode-cn.com/problems/find-m...

  • 状态压缩和状压DP

    问题:n*n的棋盘放置n个点,保证每一行,每一列都有且只有一个点,有几种放置方式? 一、组合数解法:ans=n!二...

  • POJ 3311 floyd+压状DP

    poj3311因为这道题 点N 不超过10 可以 把状态转化 为 二进制数,0表示没经过这个点,1表示经过这个点。...

  • 221. Maximal Square

    LeetCode Link 题解方式 DP

  • 排位赛第三场记录

    A - King Moves CodeForces - 710A 题解 签到题,求空棋盘上King当前位置能走的位...

网友评论

    本文标题:题解 [SCOI2005] 互不侵犯King (状压DP)

    本文链接:https://www.haomeiwen.com/subject/xgmauxtx.html