1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 2337 Solved: 1366

[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

16

刚学状压DP的蒟蒻A的第一道状压，一开始写的朴素状压，发现各种蛋疼根本就不对，（毕竟是个沙茶），于是搜了下题解（怪我啦），发现还是too young，too simple；高端的预处理让我膜拜，对于状压DP这方面现在是真的水的不行，还需要多多练习啊

此处传送门：http://blog.csdn.net/qpswwww/article/details/34516641

高端讲解！

傻×的程序附上：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int plan[1000]={0},map[1000][1000]={0},num[1000]={0};

long long f[10][100][1000]={0};

int n,k,zz=0;

void dfs(int king,int loc,int state)

{

    plan[++zz]=state;

    num[zz]=king;

    if ((king>=(n+1)/2) || (king>=k)) return;

    for (int i=loc+2; i<=n; i++)

        dfs(king+1,i,state+(1<<(i-1)));

}

int main()

{

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

    dfs(0,-1,0);

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

        for (int j=1; j<=zz; j++)

            if ((plan[i] & plan[j]) || (plan[i]>>1 & plan[j]) || (plan[i]<<1 & plan[j]))

                map[i][j]=map[j][i]=0;

            else

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

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

        f[1][num[i]][i]=1;

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

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

            {

                for (int t=1; t<=zz; t++)

                    {

                        if (num[t]>j) continue;

                        for (int l=1; l<=zz; l++)

                            if (map[l][t] && num[l]+num[t]<=j)

                                f[i][j][t]+=f[i-1][j-num[t]][l];

                    }

            }

    long long ans=0;

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

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

    printf("%lld",ans);

    return 0;

}