-1

N 本 ( N<=200) あります。それらはすべて K 人 ( K<=100) によって翻訳されなければなりません。すべての人は、インデックス S からインデックス S+D-1 (0<=D<=N) までの D 本を翻訳できます。すべての男性は、翻訳した最初の本に対して 1 ページあたり c_1 ドル、2 番目の本に対して c_2 を支払われます...

c_i for the book i.
0<=c_i<10000

書籍は、提供された順序で翻訳する必要があります。

入力:
最初の行: 2 つの数値 N および K
2 番目の行: N の数値 - 各書籍のページ数 (<=10 000)
3 番目の行: N の数値 - c_1、c_2、... c_N; c_i は、i-1 本を翻訳した人による本を翻訳するための価格です。

出力:
すべての書籍の翻訳に支払わなければならない最低価格。

例:
入力:
6 3
50 100 60 5 6 30
1 2 3 4 5 6

出力: 339
(最初の人が最初の本を翻訳した +50*1 次の人が 2 番目、3 番目、4 番目、5 番目の本を翻訳した: +100*1+60*2+5*3+6*4最後の本 +30*1 =339)
誰かこの宿題を手伝ってくれませんか? 私はそれを解決するために動的計画法を使用しなければならないことを知っています。

4

2 に答える 2

1

いくつかの手がかり: 関数 F(BookNumber, ManNumber, NumOfBooksHeHaveTranslated) を作成します。

F(1, 1, 0) から始めます。は明らかです

F(1, 1, 0) = Pages[1] * C[1] + Min(F(2, 1, 1), F(2, 2, 0))

つまり、最適なバリアントを選択する必要があります。同じトランスレータを使用するか、次のトランスレータを使用するかです。一般的なケース F(B, M, N) に対してこの関数を作成し、再帰的なソリューションを作成し、小さな入力をチェックし、再帰を DP に変換します (メソッドはアルゴ ブックに記載されています)。

于 2012-05-31T13:00:15.133 に答える
0

アルゴリズムが行う必要がある実際の選択は、一連の書籍のどの時点で、ある翻訳者から次の翻訳者に変更するかです。それが問題の唯一の決定点であり、他のすべてはそこから導かれます。これを再帰的/動的プログラミングの問題に変換できます。たとえば、N 本を K 人の翻訳者が翻訳するコストは、最初の x 本を 1 人の翻訳者が翻訳し、N - x を残りの K - 1 人の翻訳者が翻訳するコストに相当します。または、最初の x 本を n 人の翻訳者が翻訳し、N - x を残りの K - n 人の翻訳者が翻訳する費用に相当します。これは、動的計画法ソリューションで使用できる細分化/再帰ステップです。

これを行うための実際のコードを誰も投稿しないことを願っています。それは宿題です。

于 2012-05-31T12:56:14.000 に答える