【题解-Acwing】291. 蒙德里安的梦想

题目291. 蒙德里安的梦想题目描述求把 N×M 的棋盘分割成若干个 1×2 的长方形有多少种方案。例如当 N2M4 时共有 5 种方案。当 N2M3 时共有 3 种方案。如下图所示输入格式输入包含多组测试用例。每组测试用例占一行包含两个整数 N 和 M。当输入用例 N0M0 时表示输入终止且该用例无需处理。输出格式每个测试用例输出一个结果每个结果占一行。数据范围1≤N,M≤11时空限制1s / 64MB输入样例11 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0输出样例11 0 1 2 3 5 144 51205代码#includebits/stdc.husingnamespacestd;constintN12,M1N;intn,m;longlongf[N][M];boolst[M];vectorintstate[M];intmain(){while(cinnm,n||m){//计算所有状态的连续0(空行)的个数//如果是偶数个,则st为truefor(intj0;j1n;j){intcnt0;boolvalidtrue;for(inti0;in;i){//遍历这个状态所有的行或者说每一位的情况if(ji1){//该行如果是1,连续就中断了,可以统计连续0的个数if(cnt1){validfalse;break;}cnt0;}elsecnt;}if(cnt1)validfalse;st[j]valid;}//预处理每个状态是否可以成功转移//即第i-2列的状态k和第i-1列的状态j是否冲突for(intj0;j1n;j){state[j].clear();//多组数据for(intk0;k1n;k)//jk0:j和k不同时伸出来//j|k表示第i-1列的1的个数,或者看成一个状态//st[j|k]true,表示第i-1列连续的空行数为偶数if(!(jk)st[j|k])state[j].push_back(k);}memset(f,0,sizeoff);f[0][0]1;for(inti1;im;i)for(intj0;j1n;j)for(autok:state[j])f[i][j]f[i-1][k];coutf[m][0]endl;}return0;}结果