思路分析

本题其实还是很简单的，我们要想清楚状态机和状压之间的联系，我说下个人理解，状态机就是前一个阶段的决策会影响之后阶段的决策，这时才会去想状态机，本题就属于这种，前一行咋放的会影响后一行的摆放，再说说状态压缩，这就是一个技巧而已，利用位运算能搞很容易的描述出每一个阶段的所有决策的状态，所以我们就可以用这个技巧来解题了，剩下就简单了，代码在下方

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 12, M = 110;
typedef long long ll;

int n, m;
int num[1 << N];
ll dp[N][M][1 << N];

int main(){
    cin >> n >> m;
    for(int i = 0;i < 1 << n;++i)
        for(int j = i;j;j -= (j & -j))
            num[i]++;

    dp[0][0][0] = 1;
    for(int i = 1;i <= n;++i)
        for(int k = 0;k <= m;++k)
            for(int j = 0;j < 1 << n;++j)
                if((j & (j << 1)) == 0)
                    for(int t = 0;t < 1 << n;++t)
                        if((t & (t << 1)) == 0 && (t&j) == 0 && ((t|j) & (t|j)<<1) == 0 && k >= num[j])
                            dp[i][k][j] += dp[i-1][k-num[j]][t];

    ll ans = 0;
    for(int j = 0;j < 1 << n;++j) ans += dp[n][m][j];

    cout << ans << endl;
    return 0;
}