题解：P1924 贴海报
xfrvq
·
·
题解
考虑优化状态数。若 $(i-2,j)$ 可填 $(i-1,j)$ 不可填没有用。对每列维护上个不可填行在 $i-1,i-2$ 还是 $\le i-3$，状态数 $O(3^mn)$。
先预处理所有的转移 $(S,T,w)$ 代表：第 $i-1$ 行的状态 $S$ 可贴 $w$ 张海报，转移到第 $i$ 行状态 $T$。只需枚举 $S$ 爆搜第 $i$ 行填法。
由于障碍的存在，实际转移不一定是 $S\to T$。转移第 $i$ 行前，先枚举每个 $T$，若与当前行障碍列撞了则设 $T$ 非法，否则将 $T$ 的所有障碍列，上个不可填行修改为 $i$，设 $g_T=T'$。
最终转移时枚举 $(S,T)$，若 $T$ 合法则转移 $S\to g_T$。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,S,a[11],b[11],pw[11],f[155][60000],g[60000],ans;
vector<pair<int,int>> G[60000];
bool vis[155][15];
void dfs(int i,int c){
if(i >= m){
int T = 0;
for(int i = 0;i < m;++i) T += b[i] * pw[i];
G[S].emplace_back(T,c);
return;
}
b[i] = max(a[i] - 1,0),dfs(i + 1,c);
if(i + 1 < m && !max(a[i],a[i + 1]))
b[i] = b[i + 1] = 2,dfs(i + 2,c + 1);
if(i + 2 < m && max({a[i],a[i + 1],a[i + 2]}) < 2)
b[i] = b[i + 1] = b[i + 2] = 2,dfs(i + 3,c + 1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i = pw[0] = 1;i <= m;++i) pw[i] = pw[i - 1] * 3;
for(S = 0;S < pw[m];++S){
for(int i = 0,T = S;i < m;++i,T /= 3)
a[i] = T % 3,g[i] |= (a[i] == 2) << i;
dfs(0,0);
}
for(int i = 1;i <= n;++i)
for(int j = 0;j < m;++j) scanf("%d",vis[i] + j);
memset(f,-0x3f,sizeof f),f[0][pw[m] - 1] = 0;
for(int i = 1;i <= n;++i){
for(S = 0;S < pw[m];++S)
for(int j = g[S] = 0,T = S;j < m;++j,T /= 3)
if(T % 3 == 2 && vis[i][j]){ g[S] = -1; break; }
else g[S] += (vis[i][j] ? 2 : T % 3) * pw[j];
for(S = 0;S < pw[m];++S)
for(auto[T,w] : G[S]) if(~g[T])
ans = max(ans,f[i][g[T]] = max(f[i][g[T]],f[i - 1][S] + w));
}
printf("%d\n",ans);
return 0;
}
```