NC51189 Mondriaan’s Dream

題意：

n * m的矩陣，用1 * 2和2 * 1的磚快密鋪，問多少種方法：

題解：

方法1：
我們現在規定磚頭的豎放的上部分為1，磚頭的橫放或者是豎放的下部分為0

我們每兩層進行分析，分析01的關系
我們設上層為k，下層為j
因為豎磚上為1下為0，所以上下兩層&的結果必然都是0，j&k = = 0，
且j|k中連續的0均為偶數，因為豎磚和橫磚的組合只有兩種情況如下圖：
藍色字為兩行或的結果，或的結果中0只能是連續偶數個出現，不可能連續奇數個出現

方法二：
我們用01表示這個地方放不放磚
第i行只與第i-1行相關
枚舉第i-1行的每個狀態，就可以推出第i行的狀態
如果第i-1行的某處沒放，那么第i行這個位置必須放豎磚，所以對上一行狀態按位取反之后的1的位置就是放置了豎方塊的狀態。
然后枚舉這行其他點的位置，記錄答案
這個思路很常規，但也很妙

代碼：

#include<bits/stdc++.h> using namespace std;typedef long long LL;int n, m; int const N = 1e4 + 10; LL f[20][N]; int st[N]; vector<int> state[N];int main() {while (cin >> n >> m && n && m) {// 初始化memset(f, 0, sizeof f);f[0][0] = 1;for (int i = 0; i < 1 << n; ++i) state[i].clear();// 預處理stfor (int i = 0; i < 1 << n; i ++ ) {int cnt = 0;st[i] = true;for (int j = 0; j < n; j ++ )if (i >> j & 1) {//如果第j位是1 ，統計之前連續0的數量奇偶性 if (cnt & 1) st[i] = false;cnt = 0;}else cnt ++ ;//如果是第j位是0，記錄連續0的數量 if (cnt & 1) st[i] = false;}// 預處理statefor (int i = 0; i < 1 << n; ++i) {for (int j = 0; j < 1 << n; ++j) {if ((i & j) == 0 && st[i | j]) state[i].push_back(j);}}// dp轉移for (int i = 1; i <= m; ++i) {for (int j = 0; j < 1 << n; ++j) {for (int k = 0; k < state[j].size(); ++k) { // 獲得所有的合法方案f[i][j] += f[i - 1][state[j][k]];}}}printf("%lld\n", f[m][0]);}return 0; } #include <iostream> #include <cstring> #include <cstdio> using namespace std; typedef long long ll; int n,m; ll add; ll dp[2][1<<12]; void dfs(int i,int s,int cur) {if(cur==m) {dp[i][s]+=add;return;}dfs(i,s,cur+1);if(cur<m-1 && !(s&(1<<cur)) && !(s&1<<(cur+1)) )dfs(i,s|(1<<cur)|1<<(cur+1),cur+2); } int main() {while(scanf("%d%d",&n,&m),n+m){if(n*m%2) {printf("0\n");continue;}int rt=(1<<m)-1;add=1;memset(dp,0,sizeof(dp));dfs(0,0,0);for(int i=1;i<n;i++)for(int j=0;j<=rt;j++)if(dp[(i-1)%2][j]){add=dp[(i-1)%2][j];dfs(i%2,~j&rt,0);} printf("%I64d\n",dp[(n-1)%2][rt]);}return 0; }

總結

以上是生活随笔為你收集整理的NC51189 Mondriaan‘s Dream的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。