Written by razrlele
20:37 March 27, 2015
Tri Tiling
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8737 | Accepted: 4554 |
Description
In how many ways can you tile a 3xn rectangle with 2×1 dominoes?
Here is a sample tiling of a 3×12 rectangle.
Here is a sample tiling of a 3×12 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
1 2 3 4 |
2 8 12 -1 |
Sample Output
1 2 3 |
3 153 2131 |
Source
简单DP题目。
题意是给定一个3×n的矩形,然后用2×1的矩形来填满,问有多少种不同的填充方案。
令3×2为一个单位,首先要明白的是如果n为奇数的话无论如何也填不满。
对于每一个单位矩形,有下列三种方式可以填满:
然后也有下列两种方式可以作为衔接:
进而可以推出 DP[i] = 3×DP[i-1] + 2×(DP[i-2]+DP[i-3]+Dp[i-4]+ … + DP[0])
想要理解清楚这个DP思想,可以先看看下图对于DP[i]的定义:
如图所示DP[i]和DP[i-1]是前者包含后者的关系,刚开始的时候总是喜欢理解成互相独立的关系所以很容易昏了头。
DP算法其实就是数学归纳法,关键在于找出那个状态转移方程。
再来看这道题目,因为数据范围只有30,所以直接打表即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/******************************************************** * File Name: poj2663.cpp * Author: razrLeLe * Mail: razrlele@gmail.com * Homepage: https://yueyu.io * Created Time: Fri 27 Mar 2015 12:12:30 AM CST ******************************************************/ #include "vector" #include "set" #include "deque" #include "queue" #include "algorithm" #include "functional" #include "iostream" #include "cstdio" #include "cmath" #include "cstdlib" #include "string" #include "cstring" #include "string.h" #include "map" #include "cctype" #include "list" #include "stack" using namespace std; #define INF 0x3f3f3f3f #define LOCAL int main() { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif int dp[16]; dp[0] = 1; int n; for(int i = 1; i < 16; i++) { dp[i] = 3*dp[i-1]; for(int j = 0; j <= i-2; j++) dp[i] += 2*dp[j]; } while(cin >> n && n != -1) { if(n%2) cout << 0 << endl; else cout << dp[n/2] << endl; } return 0; } |