P8756 [蓝桥杯 2021 省 AB2] 国际象棋 状压dp统计情况数的一些小理解

建议有状压基础再食用：

n行m列 等价 n列m行 ，因为n比较小，int是32位足够了，我们用比特位统计每一行的状态。

本题的状态转移方程是

dp[h][i][j][num] = (dp[h][i][j][num] + dp[h - 1][j][ii][num - nums[i]])%mod;
h是行数，i和j表示本行状态和上一行状态，num表示个数。
nums[i]是情况为 i 时的bit位为1的数目，提前可以统计一下。
dp的值就是求的情况数。

很难理解，其实我们先不看i 和 j，只看行数和num，这才是dp的样子。
然后加上i和j状态压缩，就是状压dp了。

(动态规划是有条理的遍历，是全面覆盖的，num所有可以的情况都会遍历。本行i是0也会，所以只有前几行放棋子的，后面全是0也会遍历到的。)

dp代码片:

前一行和本行情况的比特位存在隔2的
和
前两行和本行情况的比特位存在隔1的情况直接略去，也就是马会互吃的情况。

//初始化
dp[0][0][0][0] = 1;//0行什么也不放。第一行肯定会摸一下，方案数是1
//for (int h = 1; h <= m; h++)
{for (int i = 0; i < (1ll << n); i++)//本行{for (int j = 0; j < (1ll << n); j++)//前一行{for (int ii = 0; ii < (1ll << n); ii++)//前两行{for (int num = nums[i]; num <= k; num++){if ((i << 2 & j) || (i >> 2 & j))continue;if ((i << 1 & ii) || (i >> 1 & ii))continue;dp[h][i][j][num] = (dp[h][i][j][num] + dp[h - 1][j][ii][num - nums[i]])%mod;}}}}
}

参考代码

int n,m,k;int countb(int aim)
{int ret = 0;for (int i = 0; i < n; i++){if (aim & (1ll << i)){ret++;}}return ret;
}void solve()
{cin >> n >> m >> k;//n行m列  等价  n列m行//n列可统计状压vector<int>nums(1 << n);for (int i = 0; i < (1ll << n); i++){nums[i] = countb(i);}vector<vector<vector<vector<int>>>>dp(m+1, vector<vector<vector<int>>>(		1ll<<n, vector<vector<int>>(1ll << n,vector<int>(k+1)	)  )	 );//第几行 本行状态 前一行状态 个数 == 方案数//dp[0][0][0][0] = 1;//0行什么也不放。第一行肯定会摸一下，方案数是1//for (int h = 1; h <= m; h++){for (int i = 0; i < (1ll << n); i++)//本行{for (int j = 0; j < (1ll << n); j++)//前一行{for (int ii = 0; ii < (1ll << n); ii++)//前两行{for (int num = nums[i]; num <= k; num++){if ((i << 2 & j) || (i >> 2 & j))continue;if ((i << 1 & ii) || (i >> 1 & ii))continue;dp[h][i][j][num] = (dp[h][i][j][num] + dp[h - 1][j][ii][num - nums[i]])%mod;}}}}}//后面都是0也包括了只在前几行放的。。//动归int ans = 0;for (int i = 0; i < (1ll << n); i++)//本行{for (int j = 0; j < (1ll << n); j++)//前一行{ans = (ans + dp[m][i][j][k]) % mod;}}cout << ans;return;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;for (int i = 1; i <= t; i++){solve();}return 0;
}