首页 > 代码库 > UVA10918 - Tri Tiling(递推)
UVA10918 - Tri Tiling(递推)
UVA10918 - Tri Tiling(递推)
题目链接
题目大意:用2?1的瓷砖去铺3?n的框,问有多少种方式。
解题思路:首先n是奇数是无解的。这题应该说是递推,应该先明白这个状态可以由前面的哪些状态推来,画图可以发现n的状态可以由n - 2这个状态?3得到,还可以由n - 4这个状态?2得到等等。所以,f(n) = 3f(n - 2) + 2 f(n - 4) + .. + 2 f(0);再写出f(n - 2)的递推式,相减可以得到化简公式:f(n) = 4f(n - 2) - f(n - 4),边界f(0) = 1,f(2) = 3.
代码:
#include <cstdio>
#include <cstring>
const int maxn = 35;
typedef long long ll;
ll num[maxn];
void init() {
num[0] = 1;
num[2] = 3;
for (int i = 4; i <= maxn - 5; i += 2)
num[i] = 4 * num[i - 2] - num[i - 4];
}
int main () {
init();
int n;
while (scanf ("%d", &n) && n != -1) {
printf ("%lld\n", num[n]);
}
return 0;
}
UVA10918 - Tri Tiling(递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。