Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

※ 引述《oin1104 (是oin的說)》之銘言：
: 題目:
: 有三個英文字
: A缺席
: L遲到
: P出席
: 一個學生不能缺席超過兩次
: 不能連續遲到三天
: 其他都算出席
: 就可以拿出席獎勵
: 問你學生的上學天數n裡面有幾種上學方法
: 可以拿到出席獎勵

思路：
差不多，就記錄：
1.幾個A
2.結尾是P,A,L還是LL
不斷從上一個狀態推過來


py code:
--------------------------------------
class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 1000000007
        A0_P = 1
        A0_L = 1
        A0_LL = 0
        A1_A = 1
        A1_P = 0
        A1_L = 0
        A1_LL = 0

        for i in range(2, n+1):

            _A0_P = A0_P + A0_L + A0_LL
            _A0_L = A0_P
            _A0_LL = A0_L
            _A1_A = A0_L + A0_LL + A0_P
            _A1_P = A1_L + A1_LL + A1_A + A1_P
            _A1_L = A1_A + A1_P
            _A1_LL = A1_L

            A0_P = _A0_P % MOD
            A0_L = _A0_L % MOD
            A0_LL = _A0_LL % MOD
            A1_A = _A1_A % MOD
            A1_P = _A1_P % MOD
            A1_L = _A1_L % MOD
            A1_LL = _A1_LL % MOD

        return (A0_P + A0_L + A0_LL + A1_A + A1_P + A1_L + A1_LL) % MOD
--------------------------------------

第一次提交出去吃了TLE
我本地跑n=10^5沒事
python的數字太大模擬好像會越來越慢
所以還是只能乖乖的把狀態都先MOD變小
學廢了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716724342.A.318.html
※ 編輯: Rushia (122.100.73.13 臺灣), 05/26/2024 19:52:38
推 oin1104: 大師
推 DJYOSHITAKA: 大濕