RGB距離

5989 ワード
DP テキストリンク

白駿1149


方法どうてきけいかくほう

import sys

n = int(sys.stdin.readline())
home = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

for i in range(1, n):
    home[i][0] = min(home[i-1][1], home[i-1][2]) + home[i][0]
    home[i][1] = min(home[i-1][0], home[i-1][2]) + home[i][1]
    home[i][2] = min(home[i-1][0], home[i-1][1]) + home[i][2]
print(min(home[n-1]))
  • 1号室の色は2号室の色と同じではありません.
  • N号の家の色はN-1号の家の色と同じではありません.
  • i(2≦i≦N-1)号住宅の色はi-1号、i+1号住宅の色と同じではない.
    • 最初は上の条件を見て、どうやって問題を解くか悩んでいました.動的計画法を使っているようですが、どんな方法でやるべきかと思います.1番目の家で何を選ぶか->2番目の家で何を選ぶか...本当はそう思っていたのですが、1行目はそのまま入れて、2行目のR位(Rを塗るなら)は1行目にGとBの中の最高値とR価格を付けて入れて~ということでした.
    コードはとても簡単です!
    JQuery|コンテキスト
    DigitalOcean に Android x86 Atom エミュレータを飼う