Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531364824000,"title":"poj 2411 Mondriaan\u0027s Dream(状态压缩dp)","dislikeCnt":2,"content":"```\n#include\u003ciostream\u003e\n#include\u003ccstdio\u003e\n#include\u003calgorithm\u003e\n#include\u003ccstring\u003e \n#include\u003cstring\u003e\ntypedef long long ll;\nusing namespace std;\nll dp[15][1\u003c\u003c12];//当第i行,达到状态j的时候,所能采取的方案数目. \nint h,w;\nbool judge(int p){ //初始化 ,横放时第j列和第j+1列都为1才合法,竖放时将第j列记作0\n//即只有成奇数次的1出现才不合法(第一行)\n for(int j\u003d0;j\u003cw;){ //前j-1列符合要求,对第j列进行判断\n if (p\u0026(1\u003c\u003cj)){ //第j列为1\n if (j\u003d\u003dw-1) return false;//j为最后一列,不可行\n if (p\u0026(1\u003c\u003c(j+1))) j+\u003d2;//第j列和第j+1列都为1 则表示横放,可行,考虑 j+2列\n else return false;//第j列为1,第j+1列都为0不可行\n }\n else j++;//第j列为0 ,则为竖放,可行\n }\n return true;\n}\nbool check(int ns,int ps){ //判断当前状态是否合法 \n for (int j\u003d0;j\u003cw; ){\n if (ns\u0026(1\u003c\u003cj)){ //第i行第j列状态为1 \n if (ps\u0026(1\u003c\u003cj)){ //第i-1行第j列状态为1,则为横放 \n if(j\u003d\u003dw-1||!(ns\u00261\u003c\u003c(j+1))||!(ps\u00261\u003c\u003c(j+1)))//第i行和第i-1行的第j+1列都必须是1,否则是非法的\n return false;\n else j+\u003d2;\n }\n else j++;//第i-1行第j列状态为0,则为竖放\n }\n else{ //第i行第j列状态为10,,则为竖放 \n if(ps\u0026(1\u003c\u003cj))j++; //第i-1行第j列的状态必须为1才合法 \n else return false;\n }\n }\n return true;\n}\nvoid Ans(){\n int n\u003d(1\u003c\u003cw)-1; \n memset(dp,0,sizeof(dp));\n for(int i\u003d0;i\u003c\u003dn;i++) //初始化第一行的状态 \n if (judge(i))dp[1][i]\u003d1;\n for(int i\u003d2;i\u003c\u003dh;i++) //逐行dp \n for (int j\u003d0;j\u003c\u003dn;j++)//第i行的状态 \n for (int k\u003d0;k\u003c\u003dn;k++)//第i-1行的状态\n if (check(j, k))dp[i][j]+\u003ddp[i-1][k];\n printf(\"%lld\\n\",dp[h][n]);\n }\n\nint main (){\n while(cin\u003e\u003eh\u003e\u003ew\u0026\u0026(h||w)){\n if(h\u00261\u0026\u0026w\u00261){ //因为小矩形的长为2,所以不可能填充面积为奇数的大矩形 \n cout\u003c\u003c0\u003c\u003cendl;\n continue;\n }\n if(h\u003cw)swap(h,w);//主要枚举的是每一列的状态,减小循环次数 \n Ans();\n } \n return 0;\n}\n\n```","threadId":31387,"likeCnt":1,"createTime":1531364824000,"isWorkbook":false,"viewCnt":2171,"openness":2,"fav":false,"id":510,"trustable":false}