1

これは、私の大学のクラスの「フラッシュテスト」で誰も正しく答えることができなかった質問です。

私たちは与えられます：

intN<1000スロットの時間

int [] C：-10 000 <= C[i]<=各スロットに対応する10000の支払い

int T：使用する必要のあるスロットの数

問題は次のように述べられています。

怠惰な労働者は、総就業日にNスロットの時間を持っています。

時間のスロットごとに、彼は特定の支払いを受け取ります（C [i]-非現実的には、これもマイナスになる可能性があります）。

彼は、最大の支払いを受け取ることができるように、正確にTスロットの間隔を選択したいと考えています。彼が作業する間隔を選択する必要があります。たとえば、[1、4]-最初のスロットから4番目のスロットまで。

問題は、彼が休憩するたびに、彼が仕事に戻ったとき、彼が怠惰な人のように再び仕事に慣れているので、彼が最初に働いたスロットは支払われないということです。したがって、[5、5]のような空の間隔を選択することもできます。これは、支払いがマイナスの場合に便利です。これらは、事前にスロットに関連付けられている支払いに関係なく、支払い0を受け取ります。

明確にするために、簡単な例を示します。

N = 5のスロットがあり、T=4を選択するとします。C = {3、9、1、1、7}

最良の解決策は間隔[1、2]です。[4、5]合計支払い額9 + 7 = 16

合計T=4スロットをカバーし、ソリューションは有効です。

4

1 に答える 1

0

問題に対する私の最初の試みですが、もっと速いものがあるかもしれません。f(i, j, t) は、N[i] がカバーされ、N[j] がカバーされるように、サブアレイ N[i, j] (i と j を含む) 内の t スポットに適合する最良の方法を示します。f(i, j, t) = max { f(i, j-1, t-1) + C[j], max_{1 < k < j - i} f(i, jk, t- 1) }. 基本ケースは、f(i, j, t) = 0 if (j - i + 1 < t)、f(i, i, 1) = 0、f(i, j, 1) = inf、および f( i、j、2) = C[i] + C[j]。私が信じている複雑さは O(N^3 * T) であり、テーブル f のサイズは N^2 * T であり、f 内では、N の追加係数を取得するために (k < j - i) の最大値を取得する必要があります。私たちの複雑さの中で。したがって、O(N^3 * T) です。うまくいけば、私は問題の何かを見落としていません。

テーブル f から解を見つけるには、max_{i,j} f(i, j, T) を実行するだけです。

于 2013-03-16T10:56:55.807 に答える