互不侵犯king (状压dp)

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

　　这道题如果普通dfs肯定会超时。为什么呢？我们发现一行中的状态是固定的，同时行与行之间的冲突情况也是固定的。而dfs重复枚举了每一行的状态，重复判断了这一行的状态是否与前一行相冲突。于是我们预处理出一行中的状态，同时预处理出两行状态的冲突情况，然后dp就行了。\(f[i][j][k]\)表示枚举到第i行，有j个国王，当前行状态的编号为k。它只能通过不与k冲突的上一行转移而来。于是就过了。

#include <cstdio>

using namespace std;

long long st[100];

int cnt[100], now[10], map[100][100];

int n, k, cntst;

long long f[10][100][100];

void dfs(int pos){

    now[pos]=1;

    long long tmp=0; ++cntst;

    for (int i=1; i<=n; ++i){

        tmp=(tmp<<1)+now[i];

        cnt[cntst]+=now[i];

    }

    st[cntst]=tmp;

    for (int i=pos+2; i<=n; ++i) dfs(i);

    now[pos]=0;

}

int main(){

    scanf("%d%d", &n, &k);

    st[0]=0; cnt[0]=0;

    for (int i=1; i<=n; ++i) dfs(i);

    for (int i=0; i<=cntst; ++i)

        for (int j=0; j<=cntst; ++j)

            if ((st[i]&st[j])==0&&

            ((st[i]<<1)&st[j])==0&&

            ((st[i]>>1)&st[j])==0){

                map[i][j]=1; map[j][i]=1;

            }

    f[0][0][0]=1;

    for (int i=1; i<=n; ++i)

        for (int j=0; j<=k; ++j)

            for (int st=0; st<=cntst; ++st){

                if (cnt[st]>j) continue;

                for (int st2=0; st2<=cntst; ++st2){

                    if (!map[st][st2]) continue;

                    f[i][j][st]+=f[i-1][j-cnt[st]][st2];

                }

            }

    long long ans=0;

    for (int i=0; i<=cntst; ++i)

        ans+=f[n][k][i];

    printf("%lld", ans);

    return 0;

}

巴特西

互不侵犯king (状压dp)

互不侵犯king (状压dp)

最新文章

热门文章