algorithm - SPOJ : Weighted Sum

Question

给你 N 个整数，A[1] 到 A[N]。您必须为这些整数分配权重，以使它们的加权和最大化。权重应满足以下条件:

1. 每个权重应该是一个正整数。
2. W[1] = 1
3. 对于 i > 1，W[i] 应该在 [2, W[i-1] + 1] 范围内

加权和定义为 S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]

例如:

n=4 , array[]={ 1 2 3 -4 } , answer = 6 when we assign { 1 2 3 2 } respective weights .

因此，据我的理解和研究，没有 Greed 解决方案是可能的。我在纸笔上写了很多测试用例，但找不到贪心策略。

任何想法/提示/方法。

Answer 1

令 dp[i][j] 等于我们可以通过分配权重 j 从 A[1..i] 得到的最大加权和code> 到 A[i]。显然 dp[i][j] = j*A[i] + max(dp[i - 1][(j - 1)..N])。有 O(N^2) 个状态，我们的循环对每个状态采用 O(N)，因此整体时间复杂度将为 O(N^3) 。为了将它减少到 O(N^2)，我们可以注意到我们的循环有很大的重叠。

如果 dp[i][j] = j * A[i] + max(dp[i - 1][(j - 1)..N])，则

dp[i][j - 1] = (j - 1)*A[i] + max(dp[i - 1][(j - 2)..N]) = (j - 1)*A[i] + max(dp[i - 1][j - 2], dp[i - 1][(j - 1)..N]) = (j - 1)*A[i] + max(dp[i - 1][j - 2], dp[i][j] - j*A[i])

这意味着递归只需要 O(1) 的时间来计算，总共给你 O(N^2) 的时间。