[BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)

发布于 2018-02-16  49 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)

Description

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

Http

BZOJ
Luogu

Tag

动态规划,状态压缩

解决思路

设\(F[i][j][S]\)表示处理到第\(i\)行,当前摆放了\(j\)个国王,当前行状态为\(S\)的方案数,枚举上一行的合法方案累加转移即可。
为了方便,可以先预处理出某一行每一种拜访方式是否合法,以及有几个国王。

代码

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

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=10;
const int inf=2147483647;

int n,K;
ll F[maxN][maxN*maxN][1<<maxN];
bool Put[1<<maxN];//标记某一种状态是否可行
int Num[1<<maxN];//某一状态摆了多少个王

int main()
{
    scanf("%d%d",&n,&K);
    for (int i=0;i<(1<<n);i++)//预处理
        if ((i&(i<<1))==0)
        {
            Put[i]=1;
            for (int j=0;j<n;j++) if (((1<<j)&i)!=0) Num[i]++;
            F[1][Num[i]][i]=1;
        }
    for (int i=2;i<=n;i++)
        for (int j=0;j<=K;j++)
            for (int S=0;S<(1<<n);S++)//枚举当前行状态
                if (Put[S]==1)
                    for (int S2=0;S2<(1<<n);S2++)//枚举上一行状态
                        if ((Put[S2]==1)&&((S&S2)==0)&&(j-Num[S]>=0)&&((S&(S2<<1))==0)&&(((S<<1)&S2)==0))
                            F[i][j][S]=(F[i][j][S]+F[i-1][j-Num[S]][S2]);
    ll Ans=0;
    for (int i=0;i<(1<<n);i++) Ans=Ans+F[n][K][i];
    printf("%lld\n",Ans);
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)


HNCJ OIer 一枚