アグロミックスの複雑さを伴うダンス

Question

ダンスコンテストに参加しようとしていて、明日は大きな一日です！私はコンテストとその順序の曲nとのリストを先験的に知っている。多くのスカウトの後、私は裁判官と自分のスキルを決定して、リストのi番目の曲、つまりscore(i)を踊ると結果を正確に予測できるようになりました。

しかし、i番目の曲の後、次のrest(i)曲、つまり曲i + 1、...、i + rest（i）を踊ることができません。私が踊ることのできる曲の数には他の制約はありません。あなたの理想的な最大合計スコアとその複雑さを計算するための効果的なアルゴリズムを与えてください。

---

だから私は、再帰がどこmax(i) = max(i + 1)または、使用して、すべての段階で、この2のうちの最高を選ぶべきであると思います。助けてもらえますか？

Answer 1

インデックス付きのn個の曲を0..n-1とします。私が歌iから始めて踊ることが自由であることを考えると、Opt（i）を最大合計得点としましょう。オプトための再発は直感的に、私たちのどちらかが歌私を踊ると、残り時間の値を取得、または私たちは、歌のI、残りを得点し、休憩後の時間の値を取得しないでください

Opt(n) = 0 
Opt(i) = max(Opt(i+1), 
      Score(i) + Opt(i + 1 + Rest(i))) for i = 0..n-1. 

です。

この繰り返しは、以前に計算された値を配列にキャッシュして、降順に評価する必要があります。実行時間はO（n）です。

Answer 2

再帰編集1、

for i: 1 -> n 
    DP(n) = max(0,(score(i)+DP(i+r)),DP(i+1)) 

場合、

r = resting interval 
0 is the situation where it is better not to dance at all :) 

あろう：説明

ベースケースが参加して追加すると、合計スコアが0

されるようにダンスしません

そうでなければ、彼は特定の曲に踊っているかどうかは分かりません。だから決定は、彼がこの曲で踊るべきかどうかまで究極の得点が最大になるように沸騰します。

彼は踊ることを決めた場合、彼はscore(i)を獲得し、残りの最大のスコアは、彼がこの曲で踊るしないことを決定した場合、スコアはDP(i+1)なりますscore(i) + DP(i + rest(i))

の値になりますのでrest(i)のために踊ることができません。

スコアを最大にしたいので、これらの2つの値の最大値を選択します。