POJ3254 | 玉米田

Portal Soruce

@赫鲁晓夫应该是最入门的状压 DP 题。按照状压 DP 套路,行为阶段,状态压缩去描述行的每一格种不种玉米。预处地形时,将不可用的位置或 1。按位与判断上下行间,该状态在该行的地形是否合法,不断从上一行转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
int main() {
const int P=1e8;int m,n,ed;
static int g[13],s[140],f[13][140];
scanf("%d%d",&m,&n);ed=1<<n;f[0][1]=1;
for(int i=1,t;i<=m;++i)
for(int j=n-1;j>=0;--j)
scanf("%d",&t),g[i]|=((t^1)<<j);
for(int i=0,flag=1;i<ed;++i,flag=1) {
for(int j=1;j<ed;j<<=1)
if(i&j&&i&(j>>1)) {flag=0;break;}
if(flag) s[++s[0]]=i;
}
for(int i=1;i<=m;++i)
for(int j=1;j<=s[0];++j)
for(int k=1;k<=s[0];++k)
if(!(g[i]&s[j]||s[j]&s[k]))
f[i][j]+=f[i-1][k],f[i][j]%=P;
for(int i=2;i<=s[0];++i) f[m][1]+=f[m][i],f[m][1]%=P;
printf("%d",f[m][1]);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。