行业资讯
POJ 2411 Mondriaan's Dream (状压DP)
)
题目求把N* M的棋盘分割成若干个1* 2的的长方形有多少种方案。例如当N2M4时共有5种方案。当N2M3时共有3种方案。输入格式输入包含多组测试用例。每组测试用例占一行包含两个整数N和M。当输入用例N0M0时表示输入终止且该用例无需处理。输出格式每个测试用例输出一个结果每个结果占一行。数据范围1≤N,M≤111≤N,M≤11输入样例1 21 31 42 22 32 42 114 110 0输出样例10123514451205题目思路每行的状态用用十进制等值的二进制表示1代表当前行有竖着的上部分0表示其他情况。阶段从第一行开始往下递推要求下一行的状态与当前按位与全为零不可能出现全为1的情况即不可能有相邻两行同列都是一个一个长方形的上一部分按位或值为零的出现必须是连续的偶数个每个样例都提前预处理1m个数。转移方程dp[i][j]dp[i-1][k]{pre[j|k] 1 j k 0}边界值dp[0][0]1,目标dp[n][0]最后一行只能是全部横着放的#includeiostream #includecstring #includecstdio #define N 12 using namespace std; long long int n,m,dp[N][1N],pre[1N]; int main() { while(cinnmn) { for(int i0; i(1m); i)//不能提前一次性处理全部样例因为状态与m有关。 { bool cnt0,tmp0; for(int j0; jm; j) { if((ij)1) tmp|cnt,cnt0;//即使i(1j),仍需计算因为不确定其前几位连续的0是否为偶数 else cnt^1; } pre[i]tmp|cnt?0:1; } memset(dp,0,sizeof(dp));//多组样例、不要忘记初始化 dp[0][0]1; for(int i1; in; i) { for(int j0; j(1m); j) { for(int k0; k(1m); k) { if((jk)0pre[j|k]) { dp[i][j]dp[i-1][k]; } } } } coutdp[n][0]endl; } }
郑州网站建设
网页设计
企业官网
![[LeetCode]326. Power of Three ★](http://pic.xiahunao.cn/yaotu/[LeetCode]326. Power of Three ★)
