競プロ初中級者100問

JOI2013予選D 暑い日々

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_d

この問題は動的計画法を用いて解くことができます。

方針

d日目に服nを着た場合のスコアをdp[d][n]として記録します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
D, N = map(int,input().split())
T = []
for d in range(D):
    T.append(int(input()))
A = []
B = []
C = []

for n in range(N):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)

dp = [[-10**8]*N for _ in range(D+1)] # 最大値を求める問題で、初日のスコアが0になるので-infで初期化

for d in range(D):
    t = T[d]
    for n in range(N):
        if A[n] <= t <= B[n]:
            if d==0:
                dp[d+1][n] = 0 # 初日はスコアが加算されない
                continue
            for m in range(N):
                dp[d+1][n] = max(dp[d][m] + abs(C[n]-C[m]),dp[d+1][n])
print (max(dp[-1]))

記事情報

  • 投稿日：2020年6月10日
  • 最終更新日：2020年6月10日