競プロ初中級者100問

JOI2015予選D シルクロード

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

動的計画法

はじめに

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

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

問題

https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_d

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

方針

都市nにm日目にいるとして、疲労度の最小値をdp[n][m]として記録します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N, M = map(int, input().split())
D = []
C = []
for n in range(N):
    d = int(input())
    D.append(d)
for m in range(M):
    c = int(input())
    C.append(c)

dp = [[10**10]*(M+1) for _ in range(N+1)]
for m in range(M+1):
    dp[0][m] = 0
for n in range(N):
    for m in range(M):
        dp[n+1][m+1] = min(dp[n+1][m], dp[n][m]+D[n]*C[m])
print (dp[-1][-1])

記事情報

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