// UVa 10918 - Tri Tiling #include <iostream> #include <string.h> using namespace std; #define integer unsigned long long int main() { int n; while (cin >> n && (n != -1)) { if (n & 1) cout << 0 << endl; else { integer T[31]; T[0] = 1; for (int i = 2; i <= n; i += 2) { T[i] = T[i - 2] * 3; for (int j = i - 4; j >= 0; j -= 2) T[i] += (T[j] << 1); } cout << T[n] << endl; } } return 0; }
This comment has been removed by the author.
ReplyDeleteWhen n=0 ,then output is coming as 1 on running this code ?How is it possible?When n is 0,the 3 x 0 does not mean anything according to me?Please explain
ReplyDeleten=0 means "how many ways can we do a 3×0 rectagle?" There is one way to get a 3x0 "rectagle": do nothing. It's not zero because it's possible to do.
DeleteWhy T[0]=1?
ReplyDeletedo nothing is one valid way to tile.
DeleteYou also can go further to reduce the formulas be: dp(n) = 4dp(n-2) - dp(n-4). Base: dp[0] = 1, dp[2] = 3, dp[4] = 11, and start from dp[5].
ReplyDelete