1. 題目 diamonds 題目描述 小keke同學非常喜歡玩俄羅斯方塊（*^*）,他最近發現傳統的俄羅斯方塊很無趣，于是他想到了一個新規則的游戲來惡心你（……，沒素質啊）。 游戲是這樣的： 給定你一個寬度為w的游戲場地，我們設高度為正無窮。現在給你3種俄羅斯方塊： 1*2的方塊 2*2的方塊 2*2的方塊去掉一個1*1的方塊 如果你明白俄羅斯方塊的規則的話，方塊在下落過程中是可以隨便旋轉的。而且是從上往下落，上面的落在下面的上面（廢話！！！） 現在給定你一個高度h，讓你求出有多少種游戲的方法，使得最后恰好落滿h的高度（最上層是齊平的）。因為這樣可以得巨多分！巨！舒服~~~~~ 輸入文件(diamonds.in) 兩個整數h,w含義如題所述 輸出文件(diamonds.out) 一個整數，為能達到要求的游戲方法的總數。 數據范圍 1<=h,w<=9,注意答案有可能很大（你懂得，用不到高精度） 樣例輸入 2 2 樣例輸出 3 2. 題目實質 用給定的三種磚講一個區域鋪滿（又是廢話） 3. 算法 DP+DFS (也就是狀態壓縮型 DP ) 首先，每一個狀態均可以由他前面的某一個狀態轉移而來，所以，滿足 DP 的無后效性，用 DP 解決。 方程十分好寫：f[I,j]:=sigma(f[I-1,k]*g[k,j]（其中狀態 k 可以轉移到狀態 j ，I 表示該狀態鋪滿的高度為高度為 I ）) 初始值 f[1,0]:=1; 因為本題中一共三種磚，所以情況會很多，這也是比較惡心人的地方，因為情況太多，有多種轉移的方法，所以不能用 Boolean 類型數組直接判斷，而應該用一個 g 數組記錄，然后用乘法原理，將方案數直接進行累加。 狀態用二進制（HASH）存儲。 將矩陣的１行看成一種狀態，則某一行矩陣的鋪磚情況可以用一個０１串表示：０表示未鋪磚，１表示已鋪了磚。 然后，狀態改變時用位運算改變。 對于上下兩行：要能用某種類型的磚鋪，必須該磚所覆蓋的區域為空。 當搜出邊界時，直接跳出。（遞歸出口） 4. 注意事項 一定要開 int64 ！ 5. 程序代碼 Leve （pascal） var n,m,i,j,k:longint; f:array[0..9,0..1024] of int64; g:array[0..1024,0..1024] of int64; procedure dfs(step,now:longint); begin if step=m+1 then begin inc(g[i,now]); exit; end; if 1<0 then dfs(step+1,now) //如果這一行不能再鋪了，就搜下一行。 else begin if (1<1) then dfs(step+1,now+1<

轉載于:https://www.cnblogs.com/SueMiller/archive/2011/08/10/2133801.html

總結

以上是生活随笔為你收集整理的解题报告 Diamonds的全部內容，希望文章能夠幫你解決所遇到的問題。

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