状压DP

 

/**************************************************************
    Problem: 1087
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:18876 kb
****************************************************************/
 
/*
    状态压缩  最多9 ->   512
    f i,j,k 表示前i行放j个 第i行状态为k的方案数 
    第一行的状态枚举判断
    接下来几行枚举判断能否放下 
*/
#include<bits/stdc++.h> 
using namespace std;
int n,m;
long long f[15][150][1000]; // 数组开小了 错了很久  
int vis[1000],num[1000] ;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<(1<<n);i++)
    {
        if((i&(i<<1))||(i&(i>>1))) continue; // pass不合法 
        int x=i,p=0;
        while(x) 
        {
            if(x&1) p++; x>>=1;
        }
        f[1][p][i]=1; // 就存在一种情况 
        vis[i]=1;num[i]=p;
    }
    for(int k=2;k<=n;k++) // 枚举行
    for(int i=0;i<(1<<n);i++) if(vis[i])  // 枚举本一次状态
    {
        for(int j=0;j<(1<<n);j++) if(vis[j]) // 枚举上一次状态
        {
            if((j&(i<<1))||(j&(i>>1))||(j&i)) continue; // pass不合法 
            for(int l=0;l+num[i]<=m;l++) // 上一层已放置了的个数 
            f[k][l+num[i]][i]+=f[k-1][l][j];
        }
    }
    long long res=0;
    for(int i=0;i<(1<<n);i++) res+=f[n][m][i];
    printf("%lld\n",res);
    return 0;
}