状态压缩dp
f[i, a, b, k]:表示已经放好了前i - 1列,第i - 2列的状态是a,第i - 1列的状态是b,共放了k匹马的方案的集合
假设第i列的状态是c
a,b和c是二进制数: 比如说c=10010, 表示第i列的第0行和第3行上面放了一匹马
根据马跳的方式,可知
$\Rightarrow$ 相邻两列的左右一位的位置上面不能同时有1
$\Rightarrow$ 间隔一列的左右两位的位置上面不能同时有1
a:i - 2列, b:i - 1列, c:i列
(a, b), (b, c)是相邻的一列, (a, c)中间间隔一列
t: 表示c中的二进制1的个数
然后就可以进行状态转移了
f[i,b,c,k] += f[i - 1, a, b, k - t]
自己最开始做的时候,在第一行怎么预处理卡了,后来看了y总代码,发现不用预处理
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 110, M = 1 << 7, mod = 1e9 + 7;
int n, m, k;
int f[N][M][M][22];
//f[i, a, b, k]:表示已经放好了前i - 1行,第i - 2的状态是a,第i行的状态是b,共放了k皮马的方案的集合
int map[M]; //map[state]表示状态state中1的个数
int get(int x)
{
int res = 0;
while(x)
{
res ++;
x -= x & -x;
}
return res;
}
int main()
{
cin >> n >> m >> k;
for(int i = 0;i < 1 << n;i ++)
map[i] = get(i);
f[0][0][0][0] = 1;
for(int i = 1;i <= m + 1;i ++)
for(int a = 0;a < 1 << n;a ++)
for(int b = 0;b < 1 << n;b ++)
{
if(a & (b >> 2) || (a >> 2) & b) continue;
for(int c = 0;c < 1 << n;c ++)
{
if(b & (c >> 2) || (b >> 2) & c) continue;
if(a & (c >> 1) || (a >> 1) & c) continue;
int t = map[c];
for(int j = t;j <= k;j ++)
f[i][b][c][j] = (f[i][b][c][j] + f[i - 1][a][b][j - t]) % mod;
}
}
int res = 0;
for(int a = 0;a < 1 << n;a ++)
for(int b = 0;b < 1 << n;b ++)
res = (res + f[m][a][b][k]) % mod;
cout << res << endl;
return 0;
}
n不是行数,m不是列数么,第i行得方案不应该是1<<m么,为啥是反的啊
因为状态是用二进制表示的, 1 << 100的话 数组存不下来
按列枚举的状态,不是按行枚举的状态