結果

問題 No.584 赤、緑、青の色塗り
ユーザー gew1fw
提出日時 2025-06-12 20:58:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,441 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 292,472 KB
最終ジャッジ日時 2025-06-12 21:02:05
合計ジャッジ時間 5,557 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    from collections import defaultdict

    N, R, G, B = map(int, sys.stdin.readline().split())
    K = R + G + B

    # 颜色编码：0=空白，1=红，2=绿，3=蓝
    # 状态：dp[i][pp][p][r][g][b]
    # 由于空间限制，使用字典存储状态
    dp = [defaultdict(int) for _ in range(N+1)]
    dp[0][(0, 0, 0, 0, 0)] = 1  # (pp_color, p_color, r, g, b)

    for i in range(N):
        current_dp = dp[i]
        next_dp = defaultdict(int)
        for state in current_dp:
            pp_color, p_color, r, g, b = state
            count = current_dp[state]
            for c in [0, 1, 2, 3]:  # 当前涂的颜色选项（0=空白）
                if c == 1:
                    if p_color == 1 or (pp_color != 0 and p_color != 0):
                        continue
                    if r + 1 > R:
                        continue
                    new_r = r + 1
                    new_g = g
                    new_b = b
                elif c == 2:
                    if p_color == 2 or (pp_color != 0 and p_color != 0):
                        continue
                    if g + 1 > G:
                        continue
                    new_r = r
                    new_g = g + 1
                    new_b = b
                elif c == 3:
                    if p_color == 3 or (pp_color != 0 and p_color != 0):
                        continue
                    if b + 1 > B:
                        continue
                    new_r = r
                    new_g = g
                    new_b = b + 1
                else:  # c=0，空白
                    new_r = r
                    new_g = g
                    new_b = b

                # 检查三个连续的涂色情况
                if pp_color != 0 and p_color != 0 and c != 0:
                    continue  # 三个连续涂色，不允许

                new_pp_color = p_color
                new_p_color = c

                next_state = (new_pp_color, new_p_color, new_r, new_g, new_b)
                next_dp[next_state] = (next_dp[next_state] + count) % MOD

        dp[i+1] = next_dp

    # 最后，检查所有状态，其中r=R, g=G, b=B，并且i=N
    total = 0
    for state in dp[N]:
        pp_color, p_color, r, g, b = state
        if r == R and g == G and b == B:
            total = (total + dp[N][state]) % MOD

    print(total % MOD)

if __name__ == '__main__':
    main()
0