JZTXT

poj 2411 状压dp入门题

发布时间 2023-11-01 19:26:04作者: HL_ZZP
Mondriaan's Dream
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 29096   Accepted: 15505

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

Sample Input

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

Sample Output

1
0
1
2
3
5
144
51205

Source

Ulm Local 2000

 

这poj复制下来的题目还挺全awa

很经典的状压dp入门题
dp的状态设计可以说绝定了这个dp的一切，之前的dp的状态设计都是在一定范围内的，都只是用这个数字来表示一个具体的值
而状态压缩的dp的状态可以表示更多的含义
这里就是用一个维度的状态来表示当前列或者是上一列的占用情况
（其实不是占用情况，但是为了好理解，先这么说，其实用01表示竖着的小矩形的开头是否在这个位置）
然后我们就可以在这种状态的表示下进行搜索路径的优化了
（除了位运算比较复杂和难调）
状压dp的共性很明显就是有一个维度的数据量非常小，只能是10这个级别的，稍微大一点就不不行，因为这个东西的时空复杂度都是指数级别的
所以还是非常好分辨的

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <string.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll f[12][1<<11];bool chek[1<<11];
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    int n,m;
    while(1)
    {
        n=read();m=read();
        if(n==0)break;
        for(int i=0;i<1<<m;i++)
        {
            bool ha_odd=0,cnt=0;
            for(int j=0;j<m;j++)
            {
                if((i>>j)&1)//如果有一个1
                {
                    ha_odd|=cnt;
                    cnt=0;
                }
                else cnt^=1;
            }
            chek[i]=(ha_odd|cnt)?0:1;
        }
        f[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<1<<m;j++)//枚举上一个状态的1的位置 ，也就是上一个状态占掉了那些位置
            {
                f[i][j]=0;
                for(int k=0;k<1<<m;k++)//枚举下一个状态有那些竖着的    
                {
                    if((j&k)==0 && chek[j|k])
                    {
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
        cout<<f[n][0]<<endl;
    }
    return 0;
}

能学的主要就是那几个位运算的操作，还有这个预处理的思路，以及状态表示的是是否是竖着的小矩形的开头，这个我原本设计的状态不是这样的，然后很难搞
但是想想我们其实是同时有上下两排的状态的，那确实是只要记录一下开头就可以了，后效性的处理也可通过这种从后往前的方法考虑来消除，也是因为这种操作的后效性有限，如果是无限或者是不可知的那就不行了。
所以可系统的预测的后效性常常可以接受的。学到了