最後のアルゴリズミックダンス

Question

[前の関連する質問：A dance with an aglorithm's complexity]

物語：私は特定の順序でN歌とダンスのコンテストに参加しようと思います。しかし、私は各踊りの前に準備する時間があり、後で休む時間が必要なので、すべての曲に踊ることはできません。 （幸いなことに、1つのダンスから、残りの時間は、次の準備期間と重複することができます。）

私は私が私がダンスを行う曲ごとに取得することができますスコア知っている、と私は私の合計スコアを最大化します。

だから、私は3つの配列している：

• は（I）スコア私は歌＃に合わせて踊るために得ることができるスコアです。私は
• 予備校（私はは）私は歌＃直前にスキップする必要が曲数で、または他の私は歌＃を行うことはできません。 （準備（4）  =   2私は歌＃2と曲の＃3の両方をスキップしていない限り、私は歌＃4に合わせて踊ることができない場合、例えば。）
• 残り（I）は、歌＃の直後にスキップする必要がある曲の数です。曲番号iを実行した場合は、 （2 残り（4）  =  場合、私は歌＃4に合わせて踊るたとえば、その後、私は曲の＃5と曲の＃6の両方をスキップする必要があります。）

どちら予備校（ i）でもでも、（i）は上限を超えているので、Mとなります。

スコアを最大化するにはどうすればよいですか？その複雑さは何ですか？

---

私の試み：すでに与えられた回答に基づいて

、その

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

取ると、我々はデッドタイムとしてのようなものがあるように、その上に構築：

Opt(i + 1 + max(prep(i), rest(i))) 

を

私はリンクされた質問に記載されているように、iが下降すべきであることを心配しています。誰でも助けてくれますか？そのオーバーラップは私を混乱させる。この場合

Answer 1

# Get the first song that can be danced to assuming he danced to `i` and wanted to wait till prep time of a song 
def myPrep(i): 
    for j in range(i+1,n): 
     if j - prep(j) > i: 
      return j 

for i in range(0,n-1): 
    Opt(i) = max(Opt(i+1), 
       (Score(i) + Opt(i + 1 + rest(i))), 
       (Score(i) + Opt(i + 1 + myPrep(i))) 
      ) 

、私は三つの可能性を考えています：

• スキップ現在の曲 - 現在の曲へ>Opt(i+1)
• ダンス - >休憩のためのScore(i)と
  • 待ちithの曲または
  の
  • のエノを提供する最初の曲を待つぐふ準備時間 - >myPrep(i)

は私がith後に十分な準備時間を持っているすべての可能な曲を含める必要がある場合は、自分自身と議論が、その後Opt(myPrep(i))は、右の番号を取得する必要があり、したがって、私たちがいないと思いましたmyPrep(i)の後にすべての曲を含める必要がありますithの曲