DP做题笔记

2026.5

5.13：

P8756国际象棋

说实话，状压dp大多数题还是很明显的，这道题就不例外，典型的棋盘上状压。

定义：\(dp[i][s][j][k]\) 表示第 \(i\) 行状态为 \(s\)，上一行状态为 \(j\)，放了 \(k\) 个马的方案数。

转移方程就是：\(dp[i][s][j][k] = dp[i][s][j][k] + dp[i - 1][j][h][k - cnt[s]]\)，其中 \(h\) 表示上上行的状态，\(cnt[s]\) 表示状态 \(s\) 的1的个数。

Ac Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = (1 << 6);
const int mod = 1e9 + 7; 
inline int read(){char ch; int f = 1,res = 0; ch = getchar();while (!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while (isdigit(ch)) {res = res * 10 + (ch - '0'); ch = getchar();}return res * f;
}
inline void write(int x){if (x < 0) putchar('-'),x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');return;
}
int n,m,K;
long long ans = 0;
long long dp[110][maxn][maxn][30];
signed main(){memset(dp,0,sizeof(dp));n = read(); m = read(); K = read();for (int i = 0;i < (1 << n);i++) dp[1][i][0][__builtin_popcount(i)] = 1;for (int i = 2;i <= m;i++){for (int S = 0;S <= (1 << n) - 1;S++){for (int j = 0;j <= (1 << n) - 1;j++){if (S & (j << 2) || S & (j >> 2)) continue;for (int k = 0;k <= (1 << n) - 1;k++){if (S & (k << 1) || S & (k >> 1) || j & (k << 2) || j & (k >> 2)) continue;for (int h = __builtin_popcount(S);h <= K;h++){dp[i][S][j][h] += dp[i - 1][j][k][h - __builtin_popcount(S)];dp[i][S][j][h] %= mod;}}}}}for (int j = 0;j < (1 << n);j++){for (int k = 0;k < (1 << n);k++){ans = (ans + dp[m][j][k][K]) % mod;}} cout << ans;return 0;
}