九度 oj 题目1552：座位问题

http://ac.jobdu.com/problem.php?pid=1552

参考了http://cloud.300206.net/detail/50611081187009983838.html

动归，分最后一个是男还是女讨论。注意当总共有0人以男结尾的排列是1种情况。 

#include <cstdio> #define inone(i) scanf("%d",&i) const int maxn = 1e3 + 10; int m[maxn], f[maxn], n; void init() { f[0] = 0, f[1] = 0, f[2] = 1; m[0] = 1, m[1] = 1, m[2] = 1; for (int i = 2; i <= maxn; i++) { f[i] = (m[i - 2] + f[i - 1]) % 1000000007; m[i] = (m[i - 1] + f[i - 1]) % 1000000007; } } int main() { init(); while (inone(n) != EOF) { printf("%d\n", (f[n]+m[n])% 1000000007); } return 0; }