状压DP棋盘放置问题如何解决？
摘要：其实没什么好说的，就是在棋盘上的。 题目 P2915 [USACO08NOV] Mixed Up Cows G(混入的) 这个应该算是旅行商问题。 解法 状态定义: (dp_{i,state}) 表示选择状态为 (state)，以第
其实没什么好说的，就是在棋盘上的。
题目
P2915 [USACO08NOV] Mixed Up Cows G(混入的)
这个应该算是旅行商问题。
解法
状态定义:
\(dp_{i,state}\) 表示选择状态为 \(state\)，以第 \(i\) 头奶牛为结尾的方案数。
状态转移方程式
\[dp_{j,s|(1<<j)} = \sum dp_{i,s}
\]
哦对了！不要忘记了特殊条件！
相邻奶牛的编号之差均超过K
代码
戳我喵~
int a[17];
lint dp[17][(1 << 16) + 10];
int main() {
int n = re, k = re;
for (int i = 0; i < n; i++) a[i] = re;
for (int i = 0; i < n; i++) dp[i][1 << i] = 1;
for (int s = 0; s < (1 << n); s++) {
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) {
for (int j = 0; j < n; j++) {
if (!((s >> j) & 1) && abs(a[j] - a[i]) > k) {
dp[j][s | (1 << j)] += dp[i][s];
}
}
}
}
}
lint ans = 0;
for (int i = 0; i < n; i++) ans += dp[i][(1 << n) - 1];
wr(ans), endl;
}
P1879 [USACO06NOV] Corn Fields G
这题太经典了！
解法
先看数据范围：\(1 \le n,m \le 12\)
可以状压！
我们注意力惊人，发现了只有与它相邻的行与列才有关，所以我们考虑压缩一行的状态。
所以我们定义 \(dp_{i,j}\) 表示第 \(i\) 行，采用了第 \(j\) 个合法状态时的方案总数。
可是合法状态怎么统计呢？
我们可以在预处理阶段处理这合法状态。
合法状态即满足题目的条件，即不能有两块奶牛所在的草地相邻。
我们只需要判断 i & (i >> 1) 是否为 \(0\)，如果为 \(0\)，那么它就是中意的方案。
最后的 \(DP\) 还算简单，看代码就能理解。