Loj10170骑士

试题描述

在 n×n（1≤n≤10）的棋盘上放 k（0≤k≤n）个国王（可攻击相邻的8个格子），求使它们无法互相攻击的方案总数。

输入

输入有多组方案，每组数据只有一行为两个整数n和k。

输出

每组数据一行为方案总数，若不能够放置则输出 0。

输入示例

样例输入 1
3 2
样例输入 2
4 4

输出示例

样例输出 1
16
样例输出 2
152

这道题看上去很像八皇后，但是变成的国王以后无疑会增加很多情况，暴力会炸。而因为国王只影响到上下左右八个各自，所以我们能用状压DP解决。

设f[i][j][k]表示第i行，第j种状态下，一共有k个国王的情况。其中j是一个二进制数，比如74代表的是它的二进制1001010代表的是这一行的国王摆放情况。

然后预处理num[i]代表i这种状态需要的国王数，比如num[74]=3

转移方程就是：f[i][j][k]+=f[i-1][t][k-num[j]];其中k、t分别表示当前行的状态和上一行的状态。其中保重k、t互相满足。

代码如下：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <queue>

#include <stack>

#include <vector>

using namespace std;

#define MAXN 155

#define INF 10000009

#define MOD 10000007

#define LL long long

#define in(a) a=read()

#define REP(i,k,n) for(int i=k;i<=n;i++)

#define DREP(i,k,n) for(int i=k;i>=n;i--)

#define cl(a) memset(a,0,sizeof(a))

inline int read(){

    int x=,f=;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;

    for(;isdigit(ch);ch=getchar()) x=x*+ch-'';

    return x*f;

}

inline void out(int x){

    if(x<) putchar('-'),x=-x;

    if(x>) out(x/);

    putchar(x%+'');

}

LL n,m,total,f[][MAXN][MAXN],num[MAXN],s[MAXN],ans;

int main(){

    in(n);in(m);

    REP(i,,(<<n)-){

        if(i&(i<<))  continue;

        int k=;

        REP(j,,n-)  if(i&(<<j))  k++;

        s[++total]=i;

        num[total]=k;

    }

    f[][][]=;

    REP(i,,n)

        REP(j,,total)

            REP(k,,m)

                if(k>=num[j])

                    REP(t,,total)

                        if(!(s[t]&s[j]) && !(s[t]&(s[j]<<)) && !(s[t]&(s[j]>>)))

                             f[i][j][k]+=f[i-][t][k-num[j]];

    REP(i,,total)  ans+=f[n][i][m];

    cout<<ans;

    return ;

}

巴特西

Loj10170骑士

最新文章

热门文章