poj2411 答题报告

poj2411 解题报告

题目：给你一个h*w的矩形，用一个1*2的小矩形去填充，问有多少种填充方法，不考虑对称性

详细的解题报告参考：

http://www.2cto.com/kf/201208/146894.html

下面描述代码实现

#include <stdio.h>
#include <string.h>

#define swap(x, y) do { \
	int t; \
	t = x; \
	x = y; \
	y = t; \
}while(0) \

#define MAXN 1<<11

long long  f[2][MAXN];
long long  ans[12][12];
int width;

int test11(int x) 
{
	while (x) {
		if (x&0x1) {
			if (x&0x2) 
				x >>= 2;
			else
				return 0;
		} else {
			x >>= 1;
		}
	}
	return 1;
}

int testState(int x, int y)
{
	if ((x|y) != width-1) return 0;
	return test11(x&y);
}

int main()
{
	int m, n;
	int i, j, k;
	memset(ans,-1,sizeof(ans));
	while (scanf("%d %d", &m, &n) && (m!= 0 || n!=0)) {
        if(ans[m][n] != -1) {
            printf("%lld\n", ans[m][n]);
            continue;
        }
		if (m < n) swap(m, n);
		if (n == 0 || (0x1&m&n) == 1) {
			printf("0\n");
			ans[m][n]=ans[n][m]=0;
			continue;
		}

		width = 1<<n;
		for (i = 0; i < 2; i++)
			for (j = 0; j < width; j++)
				f[i][j] = 0;

		for (i = 0; i < width; i++) {
			if (test11(i))
				f[0][i] = 1;
		}
/*
		for (i = 1; i < m; i++) {
			for (j = 0; j < width; j++){
				long long tmp = 0;
				for (k = 0; k < width; k++) {
					if(testState(j, k))
						tmp += f[(i-1)%2][k];
				}
				f[i%2][j] = tmp;
			}
		}
*/
       /*剪枝优化*/
        for (i = 1; i < m; i++) {
            memset(f[i%2], 0, sizeof(f[0]));
            for(k = 0; k < width; k++) {
                  if (!f[(i-1)%2][k]) continue;
                  for (j = 0; j < width; j++) {
                      if (testState(j, k))
                         f[i%2][j] += f[(i-1)%2][k];
                  }
            }
        }
        ans[m][n]=ans[n][m]=f[(m-1)%2][width-1];
		printf("%lld\n", ans[m][n]);
	}
	return  0;
}

解题思路给出的把铺砖问题转换成填0和1的问题，还是不太明白怎么想到，竖着的要填0,1。。。。