【hiho一下 第四十一周】骨牌覆盖问题·一

17748018

对于这个题目，采用动态规划的方法来解决。我们只需要考虑当前步骤如何来摆放骨牌，后续的即可转化为子问题。

从上面图中，我们可以清楚的看出，在每一步摆放骨牌的时候，要么是竖着放1块骨牌，要么是横着放2块骨牌，而且显然竖着放1块和横着放两块是不同的两种方案，其构成的是不同的解决方案。如果我们用f（n）来表示长度为n时的解决方案数，那么我们可以将其化为两个子问题：

1. 如果我们第一步放置一个竖着的骨牌，则其后面的n-1个棋盘有f（n-1）种摆法；
2. 如果我们第一步放置两个横着的骨牌，则其后面的n-2个气派有f（n-2）种摆法。

这就是斐波那契数列了。

#include <stdio.h>int count(int n) {if (n < 1)return 0;else if (n <= 2)return n;int arg1 = 1, arg2 = 2, i;for (i = 3; i < n; ++i)if (i & 1) {arg1 += arg2;arg1 %= 19999997;}else {arg2 += arg1;arg2 %= 19999997;}return (arg1 + arg2) % 19999997;
}int main() {int n;while (scanf("%d", &n) != EOF)printf("%d\n", count(n));return 0;
}