題干：

In how many ways can you tile a 3xn rectangle with 2x1 dominoes??
Here is a sample tiling of a 3x12 rectangle.?

Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Sample Input

2 8 12 -1

Sample Output

3 153 2131

解題報告：

?

AC代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 200 + 5; ll dp[55][15]; int n; int main() {dp[0][7]=1;dp[1][4]=dp[1][5]=dp[1][8]=1;for(int i = 2; i<=35; i++) {dp[i][1] = dp[i-1][5];dp[i][2] = dp[i-1][6];dp[i][3] = dp[i-1][4];dp[i][4] = dp[i-1][3] + dp[i-1][7];dp[i][5] = dp[i-1][7] + dp[i-1][1];dp[i][6] = dp[i-1][2];dp[i][7] = dp[i-1][8] + dp[i-1][4] + dp[i-1][5];dp[i][8] = dp[i-1][7];}while(cin>>n&& n!=-1) {printf("%lld\n",dp[n][7]);}return 0 ; }

雖然有很多狀態都是不可能用到的（比如2和6），但還是定義一下比較好。

狀態橫著寫一下：

100

010

001

110

011

101

111

000

一定別忘了000這種狀態哈~

?

附一種錯誤的遞推：

#include<bits/stdc++.h>using namespace std; int dp[100000][3]; int n; int main() {dp[1][2] = 1;dp[1][1] = 0;dp[1][0] = 0;cin>>n;for(int i = 2; i<=n; i++) {dp[i][1] = dp[i-1][2] + 1;dp[i][0] = dp[i][1] + 1;dp[i][2] = dp[i-2][0] * 2 + dp[i-1][1];}cout << dp[n][0] << endl; return 0 ;}

?

總結

以上是生活随笔為你收集整理的【POJ - 2663】Tri Tiling （简单dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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