【洛谷 1896】互不侵犯

题目描述

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

注：数据有加强（2018/4/25）

输入格式

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

输出格式

所得的方案数

输入输出样例

输入 #1复制

3 2

输出 #1复制

16

题解：详见洛谷，因为不熟，so复制来的题解，但是看懂

#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,k;
long long dp[10][15000][80]; 
long long state[777777] , king[77777] ;
long long ans , sum;
inline void inte()
{
    int tot = (1<<n) - 1;
    for(int i = 0 ; i <= tot ; i++)
        if(!((i<<1)&i))        
            state[++ans] = i;   
            int t = i;
            while(t)             
            {
                king[ans] += t%2;
                t>>=1;            
            }
        }
 } 

int main()
{
    cin>>n>>k;                          
    inte();                             
    for(int i = 1; i <= ans ; i++)    
        if(king[i] <= k)                    
            dp[1][i][king[i]] = 1;

    for(int i = 2 ; i <= n ; i++)                          
        for(int j = 1; j <= ans ; j++)                     
            for(int p = 1; p <= ans ; p++)               
            {                                            
                if(state[j] & state[p]) continue;                
                if(state[j] & (state[p]<<1))    continue;     
                if((state[j]<<1) & state[p])    continue;     
                for(int s = 1 ; s <= k ; s++)
                {                                              
                    if(king[j] + s > k) continue;                
                    dp[i][j][king[j]+s] += dp[i-1][p][s];       
            }

    for(int i = 1; i <= n ; i++)                        
        for(int j = 1 ; j <= ans ; j++)                 
            sum += dp[i][j][k];                         

    cout<<sum;
    return 0;   

}