acwing 1064. 骑士

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

输入格式

共一行，包含两个整数 n和 k。

输出格式

共一行，表示方案总数，若不能够放置则输出0。

数据范围

1≤n≤10,
0≤k≤n^2

输入样例：

3 2

输出样例：

16

解题报告：f[i][j][k]对应的就是第i行状态为j，已经选了k个国王的方案的集合，状态转移方程，如果盲算，ijk*状态j的枚举=1e9，应该会超时，但是我们可以把合法的状态已经某一个状态对应的状态存起来，这样就能优化不少了，接下来想想状态怎么转移，f[i][j][k]可以由前i-1行j`（这里指j上一行的合法状态）[k-选的国王数量]所有这样的集合转移过来，至于如何判断是否是合法状态，第一存在相邻的1（相邻的国王） 肯定不合法，第二如果两行|起来有相邻的1也不行，两行&起来不能有1。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const   int N=12,M=1<<10,K=110;
typedef long long ll;
ll f[N][M][K];
int cnt[M];
vector<int>state;
vector<int>head[M];
int n,m;
bool check (int state)
{
   
    for (int i=0;i< n;i++)
    if(((state >> i)&1) && (state >> i+1 & 1))
    return false;
    return true;
}
int count(int state)
{
   
    int cnt=0;
    for(int i = 0;i < n ;i ++)
    if( state>>i&1)
    cnt++;
    return cnt;
}
int main()
{
   
    cin >> n >> m;
    for(int i=0;i< 1<<n ;i ++)
    if(check(i))
    {
   
        state.push_back(i);
        cnt[i]=count(i);    
    }
    //for(int i=0;i<state.size();i++)
   // cout<<state[i]<<' '<<cnt[state[i]]<<endl;
    for(int i=0;i<state.size();i++)
    for(int j=0;j<state.size();j++)
    {
   
        int state1=state[i] , state2=state[j];
        if(check(state1 | state2) && (state1 & state2)==0)
        head[i].push_back(j);
    }
// exit(0);
    f[0][0][0]=1;//什么也不选也是一种方案
    for(int i=1;i<=n+1;i++)
    for(int j=0;j<state.size();j++)
    for(int k=0;k<=m;k++)
    {
      
    for(int jj=0;jj<head[j].size();jj++)
    if(k>=cnt[state[head[j][jj]]])		//当然，国王数不够用就不能转移。
    f[i][j][k]+=f[i-1][head[j][jj]][k-cnt[state[head[j][jj]]]];     
    }
    cout<<f[n+1][0][m]<<endl;//传统的方案应该把第n层数量为m的都加起来，看到大佬写的可以用第n+1啥也不选的总共国王为m方案的总数，nb。
}