BZOJ 1087（ＳＣＯＩ　２００５）　互不侵犯

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 5333 Solved: 3101

[Submit][Status][Discuss]

Description

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

左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

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

Output

　　方案数。

Sample Input

3 2

Sample Output

—————————————————————————————-

题解

一看数据范围就能猜出状压dp，dp[i][k][j]表示第i行，一共放了k个棋子，状态为j的方案数。

转移方程：

    dp[i][k][j]+=dp[i-1][k-sum[j]][k]

sum[S]为状态S中1的个数。

初值为dp[0][0][0]=1;

代码

#include<bits/stdc++.h>

#define LL long long

using namespace std;

int n,K,sum[1<<10];

LL dp[15][105][1<<10],ans;

inline int update(int x){

    int cnt=0;

    for(;x;x>>=1)

        if(x&1) cnt++;

    return cnt;

}

int main(){

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

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

        sum[i]=update(i);

    dp[0][0][0]=1;

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

        for(register int j=0;j<1<<n;j++)

            if(!((j&(j<<1)) or (j&(j>>1)))){

                for(register int k=0;k<1<<n;k++)

                    if(!(k&(k<<1) or k&(k>>1) or (k&j) or ((k<<1)&j)

                    or ((k<<1)&(j<<1)) or ((k>>1)&(j>>1)) or((k>>1)&j))

                    and sum[k]+sum[j]<=K){

                        for(register int o=sum[k]+sum[j];o<=K;o++)

                            dp[i][o][j]+=dp[i-1][o-sum[j]][k];

                    }

            }

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

        ans+=dp[n][K][i];

    cout<<ans<<endl;

    return 0;

}

巴特西

BZOJ 1087（ＳＣＯＩ　２００５）　互不侵犯

—————————————————————————————-

题解

代码

最新文章

热门文章

巴特西

BZOJ 1087（ＳＣＯＩ ２００５） 互不侵犯

—————————————————————————————-

题解

代码

最新文章

热门文章

BZOJ 1087（ＳＣＯＩ　２００５）　互不侵犯