【bzoj1087】[SCOI2005]互不侵犯King

2015.06.11 11:08 Thu | 30次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

题解

又是一道简单的状压dp,用dp[i][j][k]表示前i行放j个国王最后一行状态为p时的方案数,转移我就不说了,可以加一点简单的优化,然后判断相邻两行的状态是否冲突我用了一个自认为很简单的方法,就是预处理c[i][j]那段。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long dp[10][85][1000];
int can[1000],c[1000][1000];
int n,K;
void dfs(int now,int ret,int sum)
{
    if(now==n)
    {
        can[ret]=sum;
        return;
    }
    dfs(now+1,ret<<1,sum);
    if(~ret&1) dfs(now+1,ret<<1|1,sum+1);
}
int main()
{
    cin>>n>>K;
    memset(can,-1,sizeof(can));
    dp[0][0][0]=1;
    dfs(0,0,0);
    for(int i=0;i<(1<<n);i++)
    for(int j=0;j<(1<<n);j++)
    {
        if(i&j) c[i][j]=1;
        if(i&(j<<1)) c[i][j]=1;
        if(j&(i<<1)) c[i][j]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int k=0;k<(1<<n);k++)
        if(can[k]!=-1)
        {
            for(int p=0;p<(1<<n);p++)
            if(can[p]!=-1&&!c[k][p])
            {
                for(int j=0;j<=K-can[p];j++)
                dp[i][j+can[p]][p]+=dp[i-1][j][k];
            }
        }
    }
    long long ans=0;
    for(int i=0;i<(1<<n);i++) ans+=dp[n][K][i];
    cout<<ans<<endl;
}```