题解 P5074 【Eat the Trees】

插头dp弱化版。 因为允许多个回路，所以没必要用括号序列（~~丧心病狂地用也没人阻止你~~）括号序列是为了防止提前闭合才使用的。本题直接存轮廓线上有无插头即可。 1. 左0上0=>下1右1（加转角） 2. 左1上1=>下0右0(闭合回路) 3. 左0上1=>下1右0（直走）下0右1（转弯） 4. 左1上0=>下1右0（转弯）下0右1（直走） 情况3，4本质相同，可以归在一类里 如果你不会插头dp，[右转模板题](https://www.luogu.org/problemnew/show/P5056) 上代码 ```cpp #include <bits/stdc++.h> using namespace std; int T,n,m,a[15][15]; const int MAX = 1 << 13; //m+1位 long long dp[2][MAX]; inline int query(const int &val,const int &pos) {return val & (1 << (pos - 1));} //查询val的第pos位 inline void ch(int &val,const int &pos,const int &vv) {val &= ~(1 << (pos - 1));val |= (vv << (pos - 1));} //把val的第pos位改成vv long long work() { scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) scanf("%d",&a[i][j]); memset(dp,0,sizeof(dp)); int now = 0,pre = 1;dp[pre][0] = 1;//初始化，dp滚动 for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { for (int k = 0;k < (1 << (m + 1));k++) { int cur = k,left = query(k,j),up = query(k,j + 1); if (a[i][j] == 0) { if (!left && !up) dp[now][k] += dp[pre][k]; continue; } if (!left && !up) ch(cur,j,1),ch(cur,j + 1,1),dp[now][cur] += dp[pre][k];//情况1 else if (left && up) ch(cur,j,0),ch(cur,j + 1,0),dp[now][cur] += dp[pre][k];//情况2 else //情况3，4 { ch(cur,j,1),ch(cur,j + 1,0);dp[now][cur] += dp[pre][k]; ch(cur,j,0),ch(cur,j + 1,1);dp[now][cur] += dp[pre][k]; } } memset(dp[pre],0,sizeof(dp[pre])); swap(now,pre); } //每一行做完以后要迁移到下一行 for (int j = (1 << m) - 1;j >= 0;j--) { dp[now][j << 1] = dp[pre][j]; } memset(dp[pre],0,sizeof(dp[pre])); swap(now,pre); } return dp[pre][0];//最后的答案中轮廓线上不应该有插头 } int main () { scanf("%d",&T); while (T--) printf("%lld\n",work()); return 0; } ```