【Hihocoder [Offer收割]编程练习赛10 B】【简单DP】出勤记录II

2019-04-14 17:42发布

站内文章 / 模拟电子
14077 0 1115

题目2 : 出勤记录II

时间限制:10000ms 单点时限:1000ms 内存限制:256MB

描述

小Hi的算法课老师每次上课都会统计小Hi的出勤记录。迟到会被记录一个L，缺席会被记录一个A，按时上课会被记录一个O。 一学期结束，小Hi的出勤记录可以看成是一个只包含LAO的字符串，例如"OOOOLOOOLALLO……"。 如果小Hi整学期缺席不超过1次，并且没有连续3次迟到，小Hi的出勤记录就算合格。   现在给出字符串的长度N，小Hi想知道长度为N的出勤记录中，合格的记录总共有多少种。   例如长度为3的合格出勤记录有19种：OOO OOL OOA OLO OAO LOO AOO OLL OLA OAL LOL LOA AOL LLO LAO ALO LLA LAL ALL。

输入

一个整数N(1 <= N <= 100000)。

输出

长度为N的合格记录总数。由于结果可能很大，你只需输出结果模109+7的余数。 样例输入 3 样例输出 19 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n; int f[100010][3][4], ans[100010]; int main() { f[0][0][0] = 1; for (int i = 0; i <= 100000; ++i) { for (int j = 0; j <= 1; ++j) { for (int k = 0; k <= 2; ++k)if (f[i][j][k]) { gadd(ans[i], f[i][j][k]); //'A' gadd(f[i + 1][j + 1][0], f[i][j][k]); //'L' gadd(f[i + 1][j][k + 1], f[i][j][k]); //'O' gadd(f[i + 1][j][0], f[i][j][k]); } } } while (~scanf("%d", &n)) { printf("%d ", ans[n]); } return 0; } /* 【题意】 小Hi的算法课老师每次上课都会统计小Hi的出勤记录。迟到会被记录一个L，缺席会被记录一个A，按时上课会被记录一个O。 一学期结束，小Hi的出勤记录可以看成是一个只包含LAO的字符串，例如"OOOOLOOOLALLO……"。 如果小Hi整学期缺席不超过1次，并且没有连续3次迟到，小Hi的出勤记录就算合格。 现在给出字符串的长度N，小Hi想知道长度为N的出勤记录中，合格的记录总共有多少种。 例如长度为3的合格出勤记录有19种：OOO OOL OOA OLO OAO LOO AOO OLL OLA OAL LOL LOA AOL LLO LAO ALO LLA LAL ALL。 【分析】 我们用f[i][j][k]表示已经考虑到了前i次出勤 缺勤次数为j，连续迟到次数为k，且合格的出勤方案数 */

热门文章