思路

这是一道状压dp的题目，在此之前我没有学过状压dp，今天上午在dalao lornd的讲解下我理解了状压dp。然而我的能力有限，不能广义上来总结状压dp这个骚操作。状压dp的精髓就在于把多个状态合并为二进制数，然后再进行子集生成。我们这里设计一个状态，这个状态包含了当行棋子的摆放方式。比如，01110代表中间三个位置放置了棋子，为了简便，我们把这个状态可以直接压缩成14这个十进制的数字。这就是状态压缩。

我强烈建议读者学习完位运算的基本知识之后再来阅读状态压缩的文章，这样理解起来才能事半功倍。

之后我们搞懂了如何压缩状态之后，我们来进行dp。首先我们先要来预处理，预处理的几个目标是：计算单行的状态，计算两行之间的状态，计算每个状态的棋子数量。

计算单行和棋子的数量的状态比较简单，在[0,2^32)之间枚举出状态，判定是否有两个1相邻。如果有的话，那么在状态表中设置成false，表示这个状态不能被利用，即不能被纳入计算。具体代码如下：

for (int i = 0; i < MAX; i++)
    {
        // check if there are pairs of 1;
        if (i & (i >> 1))
            continue;
        // checked and set it true;
        sigLine[i] = true;
        // get the number of 1 within the state and record them;
        for (int j = 1; j <= i; j <<= 1)
            if (j & i)
                king[i]++;
    }

其中我们设置MAX = 1 << n，即状态的上限。至于为什么小于MAX而不是小于等于MAX，读者可以思考这两者是否有区别。

之后我们要计算两行之间的状态，我们开一个数组叫\(doubleLine[1<<maxn][1<<maxn]\)，其中如果\(doubleLine[x][y]==true\)，说明第一行的状态为x且第二行状态为y是可以存在的，可以被纳入计算的。这样的话，不难想出用暴力的方法来进行预处理：

// the first line;
    for (int i = 0; i < MAX; i++)
        if (sigLine[i])
            // the second line;
            for (int j = 0; j < MAX; j++)
                // check if these two are valid.
                if (sigLine[j] && !(i & j) && !(i & (j << 1)) && !(i & (j >> 1)))
                    // set!
                    doubleLine[i][j] = true;

我们预处理工作差不多了，接下来我们来进行动态规划的递推编写了。首先我们先来设计方程，不难想出方程：

\(dp[前n行数][累计w个棋子][本行的状态] = 当前状态数\)

\(dp[i+1][w+king[next]][nextLine] = dp[i][w][currentLine]\)

最后，我们把在n行上、棋子数量为k的所有状态枚举一边，便可以累计得出答案。特别注意的是，这道题目需要long long的数据范围，小心溢出。

代码

// P1896.cpp
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 11;
#define ll long long
int MAX;
int n, k;
bool sigLine[1 << maxn];
bool doubleLine[1 << maxn][1 << maxn];
int king[1 << maxn];
ll dp[maxn][100][1 << maxn];

int main()
{
    cin >> n >> k;
    MAX = 1 << n;
    for (int i = 0; i < MAX; i++)
    {
        // check if there are pairs of 1;
        if (i & (i >> 1))
            continue;
        // checked and set it true;
        sigLine[i] = true;
        // get the number of 1 within the state and record them;
        for (int j = 1; j <= i; j <<= 1)
            if (j & i)
                king[i]++;
    }
    // the first line;
    for (int i = 0; i < MAX; i++)
        if (sigLine[i])
            // the second line;
            for (int j = 0; j < MAX; j++)
                // check if these two are valid.
                if (sigLine[j] && !(i & j) && !(i & (j << 1)) && !(i & (j >> 1)))
                    // set!
                    doubleLine[i][j] = true;
    for (int i = 0; i <= MAX; i++)
        if (sigLine[i])
            dp[1][king[i]][i] = 1;
    for (int i = 1; i < n; i++)
        for (int poss = 0; poss < MAX; poss++)
            if (sigLine[poss])
                for (int nextLine = 0; nextLine < MAX; nextLine++)
                    if (sigLine[nextLine] && doubleLine[poss][nextLine])
                        for (int w = king[poss]; w + king[nextLine] <= k; w++)
                            dp[i + 1][w + king[nextLine]][nextLine] += dp[i][w][poss];
    ll ans = 0;
    for (int i = 0; i < MAX; i++)
        ans += dp[n][k][i];
    cout << ans;
    return 0;
}