洛谷  P1896 互不侵犯

题目描述

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

注：数据有加强（2018/4/25）

输入输出格式

输入格式：

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

输出格式：

所得的方案数

输入输出样例

输入样例#1：

3 2

输出样例#1：

16

题解：

状态dp入门  用来学习状压很好

N最大是9  我们用一个int 数就可以表示（int有32位）

我们先单独看一行  一行所有的情况是从0 到  1<<9

先找出一行 符合要求的情况有几种（没有相邻的1） 也就是  i&(i<<1)==0

并且记录下符合题意的情况的状态

    for(int i=0;i<(1<<n);i++){
        if(i&(i<<1)) continue;
        int t=i;
        while(t){
            num[w]+=(t&1);//统计此状态中国王个数
            t>>=1;
        }
        s[w]=i;//存状态
        w++;
    }

然后开始dp  我们用f[ i ][ j ][ k ]  表示 前 i 行  共放了 j 个国王  且第 i 行的状态为k

状态转移方程：  枚举 b   {  f[ i ][ j ][ a ] += f [ i - 1 ] [ m ] [ b ]; }

解释一下

f [ i ][ j ][ a ]  表示 前 i 行  共放了 j 个国王  且第 i 行的状态为a。

那么第 i 行 状态a 对应的国王数量 就设为 cnt

那前 i-1 行的国王数量就是 j - cnt 咯  我们设为 m=j - cnt

第 i - 1 行的状态呢 我们可以枚举  设为b  要判断 a b 两个状态符合题意

所以  我们枚举b 把所有f [ i - 1 ] [ m ] [ b ] 加起来

然后 注意  要开longlong 

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long ll;
int n,w,k;
ll ans;
int num[1000+7];
int s[1000+7];
ll f[110][110][110];
void init(){
    for(int i=0;i<(1<<n);i++){//搜索合法状态
        if(i&(i<<1)) continue;
        int t=i;
        while(t){
            num[w]+=(t&1);//统计此状态中国王个数
            t>>=1;
        }
        s[w]=i;//存状态
        w++;
    }
    return ;
}
void dp(){
    for(int i=0;i<w;i++){
        int j=num[i];
        if(j<=k)f[1][j][i]++;
    }
    for(int i=2;i<=n;i++){//枚举行
        for(int j=0;j<=k;j++){//枚举国王数量
            for(int a=0;a<w;a++){//枚举合法状态
                int cnt=num[a];//存下合法状态的国王数
                if(cnt>j)continue;
                int m=j-cnt;//国王总数为j  那么前面的行就要有 j-cnt
                for(int b=0;b<w;b++){//枚举上一行的状态
                    int cc=num[b];
                    if(cc>m)continue;
                    if(s[b]&s[a])continue;//判断两行合法 （上下）
                    if(s[b]&(s[a]>>1))continue;（右移）
                    if(s[b]&(s[a]<<1))continue;（左移）
                    f[i][j][a]+=f[i-1][m][b];
                }
            }
        }
    }
    for(int i=0;i<w;i++)ans+=f[n][k][i];
    return ;
}
int main(){
    scanf("%d%d",&n,&k);
    init();
    dp();
    printf("%lld\n",ans);
    return 0;
}