首页 > 代码库 > poj 2411 Mondriaan's Dream 【dp】
poj 2411 Mondriaan's Dream 【dp】
题目:poj 2411 Mondriaan‘s Dream
题意:给出一个n*m的矩阵,让你用1*2的矩阵铺满,然后问你最多由多少种不同的方案。
分析:这是一个比较经典的题目,网上各种牛B写法一大堆。题解也是
我们可以定义状态:dp【i】【st】:在第 i 行状态为 st 的时候的最大方案数、
然后转移方程:dp【i】【st】 = sum (dp【i-1】【ss】)
即所有的当前行都是由上一行合法的状态转移而来。
而状态的合法性由两种铺法得到,第一种横放,注意要求前一行全满,然后竖放,上一行为空,可以留空。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <vector> using namespace std; const long long N = 15; long long dp[N][1<<N]; long long ans[N][N]; long long n,m; bool solve(long long st) { long long tmp=0; for(long long i=0; i<m; i++) { if(st&(1<<i)) tmp++; else { if(tmp%2) return false; tmp=0; } } if(tmp%2) return false; return true; } bool cmp(long long st,long long up) { for(long long i=0; i<m; i++) { if(st&(1<<i)) { if(up&(1<<i)) { if(i==m-1 || !(st&(1<<(i+1))) || !(up&(1<<(i+1)))) return false; else i++; }//否则的话竖放 } else { if(!(up&(1<<i))) return false; } } return true; } int main() { memset(ans,0,sizeof(ans)); while(~scanf("%lld%lld",&n,&m)) { if(n==0 && m==0) break; if((m*n)%2) { printf("0\n"); continue; } if(m>n) swap(m,n); if(ans[n][m]) { printf("%lld\n",ans[n][m]); continue; } memset(dp,0,sizeof(dp)); long long len = 1<<m; for(long long i=0; i<len; i++) { if(solve(i)) dp[1][i]=1; } for(long long i=2; i<=n; i++) { for(long long st=0; st<len; st++) //当前行 { for(long long k = 0; k<len; k++) //上一行 { if(cmp(st,k)) dp[i][st]+=dp[i-1][k]; } } } printf("%lld\n",dp[n][len-1]); ans[n][m] = dp[n][len-1]; } return 0; }
poj 2411 Mondriaan's Dream 【dp】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。