hiho #1482 : 出勤记录II(DP)

本文主要是介绍hiho #1482 : 出勤记录II(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

小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

这个题在比赛中也没做出来，后来补上的。

dp[i][j][k]表示当进行到i这个位置的时候的状态，j为1表示有A,j为0表示没有A.k表示当前状态连续末尾的L的数量，

#include <iostream>
#include <cstdio>
#define MOD 1000000007using namespace std;
long long dp[100009][2][3];int main()
{dp[0][0][0]=1;for(int i=1; i<=100009; i++){for(int j=0; j<2; j++){for(int k=0; k<3; k++){///放O,那么末尾L的数量肯定是0dp[i][j][0]+=dp[i-1][j][k];dp[i][j][0]%=MOD;///放A，那么末尾L的数量肯定是0if(j)dp[i][j][0]+=dp[i-1][j-1][k];dp[i][j][0]%=MOD;///放L，那么末尾L的数量肯定至少一个Lif(k)dp[i][j][k]+=dp[i-1][j][k-1];dp[i][j][k]%=MOD;}}}int n;scanf("%d",&n);long long ans=0;for(int j=0; j<2; j++){for(int k=0; k<3; k++){ans+=dp[n][j][k];ans%=MOD;}}printf("%lld\n",ans);return 0;
}

这篇关于hiho #1482 : 出勤记录II(DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---