首页 > 代码库 > zoj 2563 Long Dominoes
zoj 2563 Long Dominoes
题目大意
用1*3的骨牌覆盖一个n*m的矩阵，求方案数。
分析
m大小为9，状态压缩dp的标志，1*3的骨牌与上两层有关，故可以用2^18来表示状态，横放或者竖放，算一下时间复杂度 30*9*2^18=300000000，而题目只给了2s，晕，故这个题就是卡这种方法，于是就需要转换一下方法了，还是用状态压缩dp，不过这次改成3进制来表示
0 表示横放或者竖放的第三个格子
1 表示竖放的第一个格子
2 表示竖放的第二个格子
转移的有三个转移
对应的上一行格子的数为
0 表明这一行可以放横，也可以放竖的第一个格子
1 表明这一行竖的第二个格子
2 这一行只能放竖的第三个格子
这样程序就不会超时了
#include<iostream>#include<cstdio>#include<cstdlib>#include<ctime>#include<cstring>#include<string>#include<set>#include<cmath>#include<stack>#include<queue>#include<vector>#include<algorithm>#include<sstream>#define inf 0x3f3f3f3f#define PI acos(-1.0)#define eps 1e-6#define LL long long#define MEM(a,b) memset(a,b,sizeof(a))#define PB push_back#define MK make_pair#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);#define BUG printf("bug************bug************bug\n");using namespace std;LL dp[31][20000],P_3[20];LL n,m,row,state;int num[20];void init(){ P_3[0]=1; for (int i=1;i<20;i++) P_3[i]=P_3[i-1]*3; //for (int i=1;i<20;i++) printf("%lld ",P_3[i]); printf("\n");}void get_bit(){ MEM(num,0); int k=0; LL ss=state; while(ss) { num[k++]=ss%3; ss/=3; }}void dfs(LL p,LL s){ if (p==m) {dp[row+1][s]+=dp[row][state]; return; } if (num[p]==0) { if (p+2<m && num[p+1]==0 && num[p+2]==0) dfs(p+3,s); dfs(p+1,s+P_3[p]); } if (num[p]==1) dfs(p+1,s+2*P_3[p]); if (num[p]==2) dfs(p+1,s);}int main(){ init(); while(scanf("%lld%lld",&m,&n)!=EOF && n+m) { if ((n*m)%3!=0) {printf("0\n"); continue; } LL maxn=P_3[m]; MEM(dp,0); dp[0][0]=1; for (row=0;row<n;row++) { for (state=0; state<maxn;state++) { if (dp[row][state]) { get_bit(); dfs(0,0); } } } printf("%lld\n",dp[n][0]); } return 0;}
zoj 2563 Long Dominoes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。