首页 > 代码库 > 【UVa】Tiling Dominoes
【UVa】Tiling Dominoes
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2245
题意：求用1×2的棋子摆满n×m的棋盘的方案数。（n×m<=100）
#include <bits/stdc++.h>using namespace std;long long d[2][1<<10], n, m;int main() { while(~scanf("%d%d", &n, &m)) { if(m>n) swap(m, n); int now=0, last=1, all=(1<<m)-1, up=1<<(m-1); for(int i=0; i<=all; ++i) d[last][i]=0; d[last][all]=1; for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) { for(int s=0; s<=all; ++s) d[now][s]=0; for(int s=0; s<=all; ++s) if(d[last][s]) { int goal=(s<<1)&all; if(i!=1 && !(s&up)) d[now][goal|1]+=d[last][s]; if(j!=1 && !(s&1) && (s&up)) d[now][goal|3]+=d[last][s]; if(s&up) d[now][goal]+=d[last][s]; } swap(now, last); } printf("%lld\n", d[last][all]); } return 0;}
经典题....轮廓线dp...每个格子设状态，然后记录上面轮廓线的状态，然后考虑三种转移：
1、这个格子上边没有覆盖，当前格子也不覆盖
2、这个格子上边没有覆盖，用一块棋子覆盖上边和当前点
3、这个格子左边没有覆盖且上边有覆盖，用一块棋子覆盖左边和当前点
然后注意开long long...
【UVa】Tiling Dominoes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。