これは、私の大学のクラスの「フラッシュテスト」で誰も正しく答えることができなかった質問です。
私たちは与えられます:
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スロットをカバーし、ソリューションは有効です。