-1

我们有 N 本书 ( N<=200)。都必须由K人翻译（K<=100）。每个人都可以将 D 本书从索引 S 开始翻译到索引 S+D-1, 0<=D<=N。每个人翻译的第一本书每页支付 c_1 美元，第二本书每页支付 c_2...

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

这些书必须按照给出的顺序翻译。

输入：
第一行：2 个数字 N 和 K
第二行：N 个数字 - 每本书的页数 (<=10 000)
第三行：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 第二个人翻译第二、第三、第四和第五本书：+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

您的算法需要做的实际选择是您在书籍序列中的哪个点从一位翻译者更改为下一位翻译者。这是问题的唯一决策点，其他一切都随之而来。您可以通过观察将其转换为递归/动态规划问题，例如，K 个翻译者翻译 N 本书的成本等于一个翻译者翻译 x 个第一本书的成本和剩余的 K - 1 个翻译者翻译 N - x 本书的成本；或者，相当于 n 位译者翻译 x 本书的成本和剩余的 K - n 位译者翻译 N - x 本书的成本。这是您可以在动态编程解决方案中使用的细分/递归步骤。

我希望没有人会发布实际代码来做到这一点；这是作业。

于 2012-05-31T12:56:14.000 回答