[luoguP1896] [SCOI2005]互不侵犯King（状压DP）

传送门

先预处理出来一行中放置国王的所有情况和每种情况所用的国王个数。

f[i][j][k]表示前i行放j个国王且最后一行的状态为k的方案数

状压DP即可

#include <cstdio> #define N 1001 int n, m, cnt, ans; int a[N][2], f[10][82][N]; inline void dfs(int s, int k, int last) inline bool check(int x, int y) int main() dfs(0, 0, 0); f[0][0][1] = 1; for(i = 1; i <= n; i++) for(j = 0; j <= m; j++) for(k = 1; k <= cnt; k++) for(l = 1; l <= cnt; l++) if(j + a[l][1] <= m && check(k, l)) f[i][j + a[l][1]][l] += f[i 1][j][k]; for(i = 1; i <= cnt; i++) ans += f[n][m][i]; printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1868] 饥饿的奶牛（DP）

下一篇：2017_7台风套题

---

DP