AcWing 3494. 国际象棋——状压DP 手写笔记图解
原题链接
中等
作者:
CindyZhang
,
2024-04-09 21:19:50
,
所有人可见
,
阅读 10
3494. 国际象棋 - AcWing题库
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int C1 = 110, C2 = 1 << 6, C3 = 21, MOD = 1000000007;
int N, M, K;
int f[C1][C2][C2][C3];
bool check1(int j1, int j2){// 判别合法性 两列相邻
return ! ((j1 << 2) & j2 || (j1 >> 2) & j2);
}
bool check2(int j1, int j2){// 判别合法性 两列相隔一列
return ! ((j1 << 1) & j2 || (j1 >> 1) & j2);
}
int get_num1(int j){// 得到摆放状态j的马的个数
int cnt = 0;
while (j){
j -= j&(-j);
cnt ++ ;
}
return cnt;
}
int main(){
scanf("%d%d%d", &N, &M, &K);
f[0][0][0][0] = 1; // 初始化,什么都没放的时候方案数为1
// 计算状态转移阵
for (int i = 1; i <= M; i ++ ){
for (int j3 = 0; j3 < 1 << N; j3 ++ ){
for (int j2 = 0; j2 < 1 << N; j2 ++ ){
if (!check1(j2, j3)) continue;// 非法摆放
for (int j1 = 0; j1 < 1 << N; j1 ++ ){
if (!check1(j1, j2)) continue;// 非法摆放
if (!check2(j1, j3)) continue;// 非法摆放
int t = get_num1(j1);
for (int k = t; k <= K; k ++ ){
f[i][j2][j1][k] = (f[i][j2][j1][k] + f[i - 1][j3][j2][k - t]) % MOD;// 状态转移
}
}
}
}
}
// 枚举最后两列状态f(M,j_n-2,j_n-1,K)并将方案数相加
int res = 0;
for (int j2 = 0; j2 < 1 << N; j2 ++ ){
for (int j1 = 0; j1 < 1 << N; j1 ++){
res = (res + f[M][j2][j1][K]) % MOD;
}
}
printf("%d\n", res);
return 0;
}