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;
}