poj2411 解题报告
#include <stdio.h>#include <string.h>#define swap(x, y) do { \int t; \t = x; \x = y; \y = t; \}while(0) \#define MAXN 1<<11long 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;elsereturn 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。。。。test11函数用于判断一个状态数字的二进制表示中，连续的1为偶数个，该函数用于初始化第一行，同时也可以用于其他行状态的判断testState函数实现判断当前行的状态是否满足条件（通过和前一行状态比较），根据解题思路中的兼容性规则，我们可以知道上下两行对应的数字是01,10,11，因此不可能是00，也就是说x|y的值肯定是width-1，而且x&y后的值满足连续的1是偶数个，这可以调用test11判断。由于DP的转移函数只与前一行有关，因此可以使用滚动矩阵来降低空间复杂度，因为需要做累加操作，使用前需要清空原先的行。main函数中的三个for语句实现了剪纸优化，优化前使用/**/中的语句，可以看到当f[(i-1)%2][k]等于0时，f[i%2][j]的值不会变化，可以剪去；且内部两个for语句调换顺序并不会影响程序执行结果，因此可以先遍历k，且只有在f[(i-1)%2][k]!=0时才遍历j。代码还使用了ans[12][12]来存储计算结果，后续相同的m*n就可以直接使用索引ans程序编写的过程中出现三个问题：1. 输出结果可能会很大，因此需要用long long类型2. f[][]改成滚动矩阵f[2][]时，起初没有考虑清除前一行的数据，导致结果不正确3. 使用ans优化时，起初申明了11*11的全局变量ans[11][11]，由于编译器越界时不会报错，且由于是全局变量，竟然可以使用ans[11][10]这样的值，只是poj一直给出wrong answer的错误，最后才发现是越界了。