[白俊-1589]1.2.3プラス4

9248 ワード
パイ 白駿 DP テキストリンク

マイコード

import sys
input = sys.stdin.readline

T=int(input())
dp=[[0,0,0] for _ in range(10001)]
dp[1]=[1,0,0]
dp[2]=[1,1,0]
dp[3]=[1,1,1]
last=4
for _ in range(T):
    n=int(input())
    for i in range(4,n+1):
        dp[i]=[dp[i-1][0],dp[i-2][0]+dp[i-2][1],dp[i-3][0]+dp[i-3][1]+dp[i-3][2]]
    
    print(sum(dp[n]))
    last=n+1

実行時間:184ミリ秒(pypy 3)


私の答え


dp整数iを1、2、3の和として表す構成は、[1最大構成、2最大構成、3最大構成]と格納される.
dp[i]の1最大構成は、dp[i-3]の1最大構成に等しい.
dp[i]の2最大構成は、dp[i−2]の1最大構成と2最大構成の和に等しい.
dp[i]の3最大構成は、dp[i−1]のすべての構成の和に等しい.

その他のコード

import sys
input = sys.stdin.readline

T=int(input())
dp=[1]*10001

for i in range(2,10001):
    dp[i]+=dp[i-2]
for i in range(3,10001):
    dp[i]+=dp[i-3]

for _ in range(T):
    print(dp[int(input())])

実行時間:72ミリ秒(python 3)


に答える


整数iを1、2、3の和の構成として表し、1が最大値を求めるときの構成、2が最大値を求めるときの構成、3が最大値を求めるときの構成で解く.
1が最大値の構成は1でなければならないので、最初からdp値を1に設定します.
2最大値の配置はdp[i]にdp[i-2]を加えればよい.
同様に、3はdp[i]+=dp[i-3]としてもよい.
上記の手順でdp[i]値を更新する限り、3が最大値の構成は2が最大値の構成には影響しません.
(その他)Systemクラスの一般的な方法