Educational DP Contest
Educational DP Contest - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
問題
C - Vacation
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
方針
配列を\(3\)つ作る。
解答
#atcoder template
def main():
import sys
input = sys.stdin.readline
#文字列入力の時は上記はerrorとなる。
#ここにコード
#input
#another version
#input
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
#output
a[0], b[0], c[0] = map(int, input().split())
for i in range(1, n):
p, q, r = map(int, input().split())
a[i] = p + max(b[i-1], c[i-1])
b[i] = q + max(c[i-1], a[i-1])
c[i] = r + max(a[i-1], b[i-1])
print(max(a[-1], b[-1], c[-1]))
#N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
main()提出結果
Submission #31651828 - Educational DP Contest
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
感想
配列長さを\(n+1\)にすれば\(i = 1\)を場合分けしなくても良いか。
#atcoder template
def main():
import sys
input = sys.stdin.readline
#文字列入力の時は上記はerrorとなる。
#ここにコード
#input
n = int(input())
a, b, c = [0] * (n+1), [0] * (n+1), [0] * (n+1)
#output
for i in range(n):
p, q, r = map(int, input().split())
a[i+1] = p + max(b[i], c[i])
b[i+1] = q + max(c[i], a[i])
c[i+1] = r + max(a[i], b[i])
print(max(a[-1], b[-1], c[-1]))
#N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
main()
コメント