大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
称号:ZOJ Problem Set – 2563 Long Dominoes
题意:给出1*3的小矩形。求覆盖m*n的矩阵的最多的不同的方法数?
分析:有一道题目是1 * 2的。比較火。链接:这里
这个差点儿相同,就是当前行的状态对上一行有影响。对上上一行也有影响。所以
定义状态:dp【i】【now】【up】表示在第 i 行状态为now 。上一行状态为 up 时的方案数。
然后转移方程:dp【i】【now】【up】 = sum ( dp【i-1】【up】【uup】 ) 前提是合法
合法性的推断是比較难考虑的一点。由于是1 * 3的。仅仅能横着放和竖着放。
假设横着放。那么上面up 和 uup 的 3 格也必须是满的才行
假设竖着放,那么up 和 uup的当前格必须是空的,注意推断后变化up
假设用简单的枚举dp的话,四层循环会超时。所以我们要用up 和 upp 来深搜构造当前行,这样才干过。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define INT long long int const long long N = 9 ; const int inf = 0x3f3f3f3f; INT dp[31][1<<N][1<<N]; int m,n; bool Judge(int s,int up,int upp) { for(int i=s;i<s+3;i++) if(!(up&(1<<i)) || !(upp&(1<<i))) return false; return true; } void dfs(int st,int cnt,int now,int up,int upp,INT num) { if(cnt==m) { dp[st][now][up]+=num; return ; } if(cnt+3<=m && Judge(cnt,up,upp)) //heng dfs(st,cnt+3,now|(1<<cnt)|(1<<(cnt+1))|(1<<(cnt+2)),up,upp,num); if(!(up&(1<<cnt))&&!(upp&(1<<cnt))) // 竖放 dfs(st ,cnt+1 ,now|(1<<cnt) ,up|(1<<cnt) ,upp , num) ; if(upp&(1<<cnt)) //留空 dfs(st ,cnt+1 ,now ,up ,upp ,num) ; } int main() { while(~scanf("%d%d",&m,&n)&& m+n) { memset(dp,0,sizeof(dp)); dfs(1,0,0,(1<<m)-1,(1<<m)-1,1); for(int i=2; i<=n; i++) { for(int up=0; up<(1<<m); up++) //上行 { for(int st=0; st<(1<<m); st++) //上上行 { if(dp[i-1][up][st]) //注意一定推断 dfs(i,0,0,up,st,dp[i-1][up][st]); } } } printf("%lld\n",dp[n][(1<<m)-1][(1<<m)-1]); } return 0; }
枚举超时代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define INT long long int const long long N = 9 ; const int inf = 0x3f3f3f3f; INT dp[31][1<<N][1<<N]; int m,n; bool isit(int st) { int tmp=0; for(int i=0;i<m;i++) { if(st&(1<<i)) tmp++; else { if(tmp%3) return false; } } if(tmp%3) return false; return true; } INT solve(int now,int up,int uup) { for(int i=0;i<m;i++) { if(!(uup&(1<<i))) //推断上上一行为0 { if(up&(1<<i)) return -1 ; else { if(!(now&(1<<i))) return -1 ; else up |= (1<<i) ; } } else { if(up&(1<<i) && now&(1<<i)) // 1 1 1 { if(i==m-2 || i==m-1) return -1 ; else if(!(now&(1<<(i+1))) || !(now&(1<<(i+2))) || !(up&(1<<(i+1))) || !(up&(1<<(i+2))) || !(uup&(1<<(i+2))) || !(uup&(1<<(i+1)))) return -1 ; i+=2; } } } return up ; } int main() { while(~scanf("%d%d",&m,&n)&& m+n) { for(int st=0;st<(1<<m);st++) { if(!isit(st)) continue; for(int up=0;up<(1<<m);up++) { if(isit(up)){ dp[2][st][up]=1; } } } for(int i=3;i<=n;i++) { for(int no = 0;no < (1<<m); no++) { for(int kp=0;kp<(1<<m);kp++) //上行 dp[i][no][kp]=0; for(int up=0;up<(1<<m);up++) //上行 { int temp ; for(int st=0;st<(1<<m);st++) //上上行 if((temp = solve(no,up,st)) != -1) dp[i][no][temp]+=dp[i-1][up][st]; //printf("%d\n",dp[i][up][up]); } } } printf("%lld\n",dp[n][(1<<m)-1][(1<<m)-1]); } return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116912.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...