出勤记录2

出勤记录Ⅱ

原题大意

小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。

算法分析

状态dp[i][j][k]表示长度为i的组合中合格的个数，i表示长度，j表示A出现的个数，k表示连续L出现的个数。

程序代码

#include <cstdio>
using namespace std;

const int mod = 1e9 + 7;
int dp[100005][2][3];

int up(int &a, int b){
    a += b;
    if(a >= mod) a -= mod;
}
int main(){

    dp[0][0][0] = 1;
    for(int i = 0; i < 100005; i++)
        for(int j = 0; j <  2; j++)
            for(int k = 0; k < 3; k++)
                {
                    up(dp[i+1][j][0],dp[i][j][k]);
                    //如果下一个是'O'
                    if(j != 1)up(dp[i+1][j+1][0],dp[i][j][k]);
                    //如果下一个是'A'，而且前面一次都没出现过
                    if(k != 2)up(dp[i+1][j][k+1],dp[i][j][k]);
                    //如果下一个是'L'，而且连续长度不超过2
                }
    int t,ans = 0;
    scanf("%d",&t);
    for(int i = 0; i < 2; i++)
        for(int j =0; j < 3; j++)
            up(ans,dp[t][i][j]);
    printf("%d\n", ans);
    return 0;
}