[アルゴリズム](イコール)アリ戦士-パイソン

教材:これはPythonでコードテストを行います
CHAPTER 8ダイナミックプログラミング
実戦問題8-3アリ戦士220 p
アリの戦士
質問する
アリ戦士は不足した食糧を補うためにバッタ村の穀倉を襲撃する準備をしている.バッタ村にはいくつかの穀倉があり、穀倉は直線である.各穀倉には一定数の食糧が貯蔵されており、アリ戦士は選択的に穀倉を略奪し、食糧を奪う.この時、バッタ偵察兵たちは一直線上に存在する穀倉の中で、隣接する穀倉が攻撃を受けると、すぐに発見される.そのため、アリ戦士は偵察兵に発見されないように、食糧倉庫を略奪し、少なくとも1つ以上の食糧倉庫を略奪しなければならない.例えば、4つの穀倉があると仮定すると、以下のようになります.
{1, 3, 1, 5}
この時、アリ戦士は2番目の穀倉と4番目の穀倉を選んだ時、最大8つの食糧を奪うことができる.アリ戦士は食糧倉庫がこのように直線的な状況でできるだけ多くの食糧を得ることを望んでいる.
アリ戦士のためにプログラムを作って、N個の穀倉に関する情報を得たとき、得られる食糧の最高価格.
入力

行目は食糧倉庫の個数Nを与えた.(3<=N<=100)

の2行目は空白に分けられ、各穀倉に貯蔵された食糧の数はKである.(0<=K<=1,000)

しゅつりょく

行目にアリ戦士が得ることができる食糧の最高価格を輸出した.

入力例

4
1 3 1 5

出力例

8

に答える
に近づく
30分も悩んだあげく、全然分からなかった.でも問題は答えを見てほとんど写したけどまだ分からない.どうして後ろは気にしなくていいの?どうして目の前の1人と2人の距離の子供だけを考えればいいの...どうして1つの部屋の子供は彼女の1つの部屋から離れた子供だけを考えて、彼女の2つの部屋から離れた子供を考えないのですか...ああ、本当に難しいですか.难しい、难しい!!!!!!!!!!!!!!!!!!!
送信

n = int(input())
arr = list(map(int,input().split()))

d=[0]*100
d[0]=arr[0]
d[1]=max(arr[0],arr[1])
for i in range(2,n):
    d[i]=max(d[i-1],d[i-2]+arr[i])

print(d[n-1])

結果

解答時間:50分/30分