[python]白駿/退社/14501号/ブルートフォース

質問する
問題リンクを終了
コンサルタントの白俊さんが会社を辞めます.
今日からN+1日で辞めるために、残りのN日にできるだけ多くの相談をします.
白俊は秘書にできるだけ多くの相談を依頼し、秘書は1日に1回異なる人に相談を手配した.
各コンサルティングは,コンサルティングを完了するのに要する時間内にTIとコンサルティングを行う際に得られる金額Piからなる.
N=7の場合は、以下のコンサルティングスケジュールを参照してください.

1日のカウンセリングは全部で3日かかりますが、カウンセリング時にもらえる金額は10です.5日間のお問い合わせは2日間かかりますが、受け付けられる金額は15です.
相談にかかる時間は1日以上かかる場合がありますので、すべての相談はできません.例えば、1日に問い合わせを行った場合、2日、3日に問い合わせをすることはできません.2日に問い合わせをすれば、3、4、5、6日には問い合わせができない.
なお、N+1日は会社にいないため、6,7日は相談できません.
退職前にカウンセリングを行う最大の利益は1日、4日、5日にカウンセリングを行うことであり、その際の利益は10+20+15=45である.
商談がうまくいけば、白俊に最大の収益をもたらす計画を立ててください.
入力
第1行はN(1≦N≦15)を与える.
2行目からN行目まで、TIとPiはスペースで区切られ、1日からN日まで順次与えられる.(1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

しゅつりょく
1行目は白俊が得られる最大の利益を出力する.

45

方法
dpテーブルを作成し、最初から最大の利益ストレージで解決

適切な入力を受け入れ、consult listにダブルリストとして保存し、一番前に[0,0]を追加します.

dpテーブルを作成し、一番前に[0]を追加

すべてのインデックスについて、2重の複文で1から現在のインデックスまでのコンサルティング時間をチェックします.

何もしていない場合、現在のdp値は前dp値(現在のdp値の最小値は前dp値)に等しいため、前dp値を現在のdp値に初期化する

現在のインデックスで終了したコンサルティングと終了したコンサルティングの前のdp値を現在のdp値と比較し、大きな値を現在のdpに格納する

コード#コード#

# url : https://www.acmicpc.net/problem/14501
# 난이도 : silver 3

import sys

input = sys.stdin.readline
n = int(input())

consult_list = [[0,0]] + [list(map(int,input().split())) for _ in range(n)]

dp = [0] * (n+1)

for i in range(1,n+1):
    dp[i] = dp[i-1]
    for j in range(1,i+1):
        if  i - j + 1 == consult_list[j][0] :
            dp[i] = max(dp[i], consult_list[j][1] + dp[j-1])


print(dp[-1])