代码拉取完成,页面将自动刷新
class Solution {
public:
/* 出现过一次旷课的都以 a 结尾 */
#define P 0 /* 未出现旷课,且这一天到校 */
#define Pa 1 /* 曾经旷课过,且这一天到校 */
#define A 2 /* 今天旷课 */
#define L1 3 /* 今天是第一天迟到 */
#define L1a 4 /* 今天第一天迟到,且之前有过旷课 */
#define L2 5 /* 已经是连续的第二天迟到了 */
#define L2a 6 /* 连续迟到第二天,且之前有旷课 */
#define MOD 1000000007u
int checkRecord(int n) {
/* dp
* 第一维:天数
* 第二维:上述各种宏定义情况
*/
vector<vector<unsigned long>> dp(n, vector<unsigned long>(7, 0));
/* 返回值 */
unsigned long ans = 0;
dp[0][P] = 1; /* 第一天到校 */
dp[0][Pa] = 0; /* 到校且之前有过旷课,不可能 */
dp[0][A] = 1; /* 第一天旷课 */
dp[0][L1] = 1; /* 第一天迟到 */
dp[0][L1a] = 0; /* 第一天迟到,且之前有旷课,不可能 */
dp[0][L2] = 0; /* 第二天迟到,不可能 */
dp[0][L2a] = 0; /* 第二天迟到,且之前有过旷课,不可能 */
for (int i = 1; i < n; i++) {
/* 第 i 天到校且没有迟到记录的情况,只能从 前一天迟到,前一天迟到两天,或者前一天到校中取得 */
dp[i][P] = (dp[i-1][P] + dp[i-1][L1] + dp[i-1][L2]) % MOD;
/* 第 i 天旷课的,只能从 前一天迟到,前一天迟到两天,或者前一天到校中取得 */
dp[i][A] = (dp[i-1][P] + dp[i-1][L1] + dp[i-1][L2]) % MOD;
/* 第 i 天迟到,且没有过旷课记录,只能从 前一天到校切没有旷课记录中选取 */
dp[i][L1] = dp[i-1][P] % MOD;
/* 第 i 天已经连续两天迟到,且没有旷课记录,只能从 前一天迟到一天中考虑 */
dp[i][L2] = dp[i-1][L1] % MOD;
/* 为了保证旷课一次的影响,所以单独分出,其余都与未旷课的情况相同 */
dp[i][Pa] = (dp[i-1][A] + dp[i-1][Pa] + dp[i-1][L1a] + dp[i-1][L2a]) % MOD;
dp[i][L1a] = (dp[i-1][Pa] + dp[i-1][A]) % MOD;
dp[i][L2a] = dp[i-1][L1a] % MOD;
}
/* 计算最后一天情况总数 */
for (int i = 0; i < 7; i++)
ans += dp[n-1][i] % MOD;
return ans % MOD;
}
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。