弱弱化版：状压&逐格转移&骨牌覆盖
详见：DP学习记录Ⅰ
弱化版：坏点，多条回路
例题：hdu 1693 Eat the Trees
将当前轮廓线状压起来，0表示有插头穿过此线，1表示没有。简单分类讨论，由上一个状态转移到下一个合法状态即可。注意一行结束后要整体左移。注意状压会多一位，因此要开够数组。需要灵活掌握二进制操作。
正确性：因为不合法状态只可能是一个格子出现多于两个插头，或者一个格子只有一个插头，而我们并没有这种转移。
关键代码：
int t = 0;
f[t][0] = 1;
for (register int i = 0; i < n; ++i) {
for (register int j = 0; j < m; ++j) {
t ^= 1; memset(f[t], 0, sizeof(f[t]));
int tp; read(tp);
for (register int s = 0; s < 1 << (m + 1); ++s) if (f[t ^ 1][s]) {
ll tmp = f[t ^ 1][s];
int lft = (s >> j) & 1, up = (s >> (j + 1)) & 1;
if (!tp) {
if (!up && !lft) f[t][s] += tmp;
} else {
f[t][s ^ (3 << j)] += tmp;
if (up != lft) f[t][s] += tmp;
}
}
}
t ^= 1; memset(f[t], 0, sizeof(f[t]));
for (register int s = 0; s < 1 << m; ++s) f[t][s << 1] = f[t ^ 1][s];
}
是不是很简单?
注意
-
众所周知，状压题下标从0开始显然更方便。 -
记得轮廓线一共有m+1处！
一条回路
例题：Gym : Pipe layout
这回我们需要知道插头之间的对应关系了。
一种易于理解的方法是最小表示法。我们用相同的数代表在轮廓线上方联通的插头，但是会出一些问题：1 1 0 2 2 0 和 3 3 0 1 1 0 表示同一种情况，这时我们需要将它们看作一种状态。方法是：
将我们遇到的第一个非零数编号为1，第二个编号为2...0永远编号为0，第二次遇到之前出现过的数沿用之前的编号。
关键代码：
const int base = 8, mask = 7;//2^3 进制存储
int b[N], bb[N];//b[i]表示原数组的第i位，bb[i]表示“i”重新编号的值。
inline int encode() {
memset(bb, -1, sizeof(bb));
bb[0] = 0;
int s = 0, bcnt = 0;
for (register int i = m; ~i; --i) {//Attention!!
if (bb[b[i]] == -1) bb[b[i]] = ++bcnt;
s <<= 3; s |= bb[b[i]];
}
return s;
}
inline void decode(int s) {
for (register int i = 0; i <= m; ++i) {//注意顺序
b[i] = s & mask;
s >>= 3;
}
}
有些状态永远用不到，比如 1 5 3 2 3，或者 1 2 1 0 2，实际用到的状态非常少，因此我们可以用哈希表存现有合法状态，优化时空复杂度，同时方便封装一些东西。（其实用 unordered map 也可以，但是正规比赛可能不让用（尽管正规比赛不太可能考插头DP））
关键代码：
const int P = 9973;
struct hashTable{
int head[NN], nxt[NN], ecnt;//模拟邻接链表存边
int state[NN];//状态的最小表示
ll val[NN];//方案数
hashTable() {
memset(head, 0, sizeof(head));
memset(nxt, 0, sizeof(nxt));
memset(state, 0, sizeof(state));
memset(val, 0, sizeof(val));
ecnt = 0;
}
inline void addedge(int s, ll v) {
int x = s % P;
for (register int i = head[x]; i; i = nxt[i])
if (state[i] == s) { val[i] += v; return ; }
++ecnt;
nxt[ecnt] = head[x];
val[ecnt] = v;
state[ecnt] = s;
head[x] = ecnt;
}
inline void clear() {
memset(head, 0, sizeof(head));
ecnt = 0;
}
inline void Roll() {
for (register int i = 1; i <= ecnt; ++i)
state[i] <<= 3;
}
}f[2];
这样，我们就可以分类讨论求解了。
ll tmp;
inline void Push(int j, int dn, int rg) {
//将第 j 个格子的下方插上个dn插头，右方插上个rg插头
b[j] = dn, b[j + 1] = rg;
f[t].addedge(encode(), tmp);
}
...
(main)
...
for (register int i = 0; i < n; ++i) {
for (register int j = 0; j < m; ++j) {
t ^= 1;
f[t].clear();
int dn = i != n - 1, rg = j != m - 1;
for (register int s = 1; s <= f[t ^ 1].ecnt; ++s) {
decode(f[t ^ 1].state[s]);
tmp = f[t ^ 1].val[s];
int lft = b[j], up = b[j + 1];
if (up && lft) {
if (up == lft) {
if (i == n - 1 && j == m - 1) Push(j, 0, 0);
} else {
for (register int k = 0; k <= m; ++k)//Attention! : k = 0
if (b[k] == lft) b[k] = up;
Push(j, 0, 0);
}
} else if (up || lft) {
int id = up | lft;
if (dn) Push(j, id, 0);
if (rg) Push(j, 0, id);
} else {
if (rg && dn) Push(j, m, m);
}
}
}
f[t].Roll();
}
if (f[t].ecnt == 0) puts("0");
else printf("%lld
", f[t].val[1]);
...
例题：P5056 【模板】插头dp
这回还有坏点。
与之前吃树题类似，如果当前格子是坏点，就只保存 0 0 -> 0 0 的转移。
另外，这回不一定是最后一行最后一列的那个格子才能接受 up == rg的情况。仔细考虑发现 up == rg 实际上就是轮廓线上方出现回路的那一瞬间，并且以后都在其它的回路上转移。因此我们只需要允许且仅允许我们最后遍历的那个格子接受up == rg 的转移即可保证仅有一条回路。
一条路径
由于路径有两个端点，插头可以突然出现或者突然消失。不过一条路径只会有两个“独立插头”（指的是突然蹦出来的端点），并且转移过程中也不会超过两个。因此我们直接将“独立插头”数量计入状态转移即可，最终答案从“独立插头”数量为2的那些状态中转移即可。
与一条回路不同的是：
-
这次转移我们还需要多枚举一个“独立插头”数量；
-
我们无法合并两个相同来源的插头(否则会出现回路）；
-
当我们发现左，上只有一个位置有插头的时候，可以让它停止；
-
当我们发现左，上一个都没有插头的时候，可以多一个下插头或右插头。
例题：Beautiful Meadow (ZOJ - 3213)
要求最大化路径上的权值和。有障碍点。
障碍点直接继承即可。因为之前我们已经特判过障碍点了，因此不会再出现不合法状态了。
for (register int c = 0; c <= 2; ++c) {
for (register int s = 1; s <= f[t ^ 1][c].ecnt; ++s) {
decode(f[t ^ 1][c].state[s]);
tmp = v + f[t ^ 1][c].val[s];
int lft = b[j], up = b[j + 1];
if (lft && up) {
if (lft == up) {
//can't merge
} else {
for (register int k = 0; k <= m; ++k)
if (b[k] == up) b[k] = lft;
Push(c, j, 0, 0);
}
} else if (lft || up) {
int id = lft | up;
if (dn) Push(c, j, id, 0);
if (rg) Push(c, j, 0, id);
if (c < 2) Push(c + 1, j, 0, 0);
} else {
tmp -= v;
Push(c, j, 0, 0);
tmp += v;
if (dn && rg) Push(c, j, m, m);
if (c < 2) {
if (dn) Push(c + 1, j, m, 0);
if (rg) Push(c + 1, j, 0, m);
}
}
}
}
注意
-
encode和decode的时候注意顺序，不要写成快读式写法了。（应该是：encode从后往前，decode从前往后） -
注意进制数通常是2的正数次幂，这样快，但是就别再老是
<<=1或者>>=1了 -
哈希表中如果查找到了 (s) 对应的那个 (x)，记得加权值后退出函数，而不能简单地
break！ -
注意
encode()和decode(int s)都是从0到m的，因为轮廓线多了一个竖线。 -
encode()中是if (bb[b[i]] == -1)而不是if (!bb[b[i]]) -
注意一开始要加上个全零（没有插头）的情况。