POJ2411Mondriaan'sDream题解--状压DP

题目链接

https://cn.vjudge.net/problem/POJ-2411#author=goodlife2017

分析

处理方法和玉米田类似,每行作为阶段,通过枚举相邻两行状态更新.

在这里怎么处理1 * 2的矩形呢?我们用1表示一个竖着的矩形的上部分,0表示其他情况,那么对于第$i$列状态x和第$i-1$列状态$y$,需满足以下条件才能转移:

  1. x&y ==0 显然
  2. x|y相邻的一段0必须有偶数个,不怎么显然。可以画一下图,或者将它们理解为横着的矩形

预处理以下直接搞就好了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=13;
const int inf=0x7fffffff;
ll f[1<<11][maxn];
int n,m;
bool ok[1<<11];
ll ans[13][13];
int main(){
    int x,y,cnt,orz_jyh;
    int sz;
    while(scanf("%d %d",&n,&m)!=EOF&&(n|m)){
    	if((n&1)&&(m&1)){puts("0");continue;}
    	if(ans[n][m]){printf("%lld\n",ans[n][m]);continue;}
        sz=1<<m;
        for(ri i=0;i<sz;i++){//连续有奇数个0的状态为0
        cnt=orz_jyh=0;
            for(ri j=0;j<m;j++){
                if((i>>j)&1)orz_jyh|=cnt,cnt=0;
                else cnt^=1; 
            }
            ok[i] = cnt|orz_jyh?0:1; //最后一位不会更新orz_jyh
        }
        //memset(f,0,sizeof(f));
		f[0][0]=1;
        for(ri k=1;k<=n;k++){//行数
            for(ri i=0;i<sz;i++){
                f[i][k]=0;
                for(ri j=0;j<sz;j++){
                    if((!(i&j))&&ok[i|j])f[i][k]+=f[j][k-1];
                }
            }
        }
        printf("%lld\n",f[0][n]);
    	ans[n][m]=f[0][n];
    }
    return 0;
}