金苹果岛 - 代码能力最大化问题

金苹果岛 - 代码能力最大化问题/n/n代码勇者来到了金苹果岛上，金苹果岛上有两种苹果：随处可见的红苹果与稀有美味的金苹果。/n/n勇者的'初始代码能力为 $1$'，他每吃下一个红苹果，代码能力就会得到一定程度的提升（每个红苹果带来的提升可能是不同的，甚至也可能是负的）；他每吃下一个金苹果，代码能力就会直接'翻倍'（每个金苹果的效果都是完全相同的）。/n/n岛上的苹果仙子用 $n$ 个红苹果和 $m$ 个金苹果招待了勇者，勇者必须吃光所有苹果。勇者必须按照仙子'规定的顺序'吃红苹果，但是他可以'自由安排'什么时候吃金苹果（可以在吃'任意'一个红苹果之前或之后吃'若干'个金苹果）。/n/n求勇者在离开金苹果岛的时候的代码能力的最大值。/n/n## 输入格式/n/n第一行输入两个正整数 $n$（$n/le10^5$）和 $m$（$ m/le10$）。/n/n第二行输入 $n$ 个整数 $a_i$（$|a_i|/le10$）。/n/n## 输出格式/n/n输出一个整数，表示勇者在离开金苹果岛的时候的代码能力的最大值。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n6 2/n1 -2 3 1 -6 5/n/n/n### 样例输出 #1/n/n/n15/n/n/n## 样例 #2/n/n### 样例输入 #2/n/n/n8 3/n5 -3 -8 2 4 -11 9 1/n/n/n### 样例输出 #2/n/n/n42/n/n/n## 提示/n/n## 样例1解释/n/n勇者吃掉红苹果 $1,-2,3,1$，代码能力变为 $4$；/n/n勇者吃掉 $2$ 颗金苹果，代码能力变为 $16$；/n/n勇者吃掉红苹果 $-6,5$，代码能力变为 $15$。/n/n这是勇者的最优方案。/n/n## 子任务/n/n对于 $10/%$ 的数据，$a_i/ge0$；/n/n对于 $30/%$ 的数据，$m=0$；/n/n对于 $70/%$ 的数据，$m=1$；/n/n对于 $100/%$ 的数据，$n/le10^5,m/le10,|a_i|/le10$。/n/n用上贪心算法写出一个正确的C++代码/n错了，小于零你就吃？内容：对于每个红苹果 $a_i$，我们可以选择吃或不吃。如果选择吃，那么我们的代码能力将增加 $a_i$；如果选择不吃，那么我们的代码能力将不变。因此，我们可以用一个变量 cur 来记录当前的代码能力。/n/n对于金苹果，我们可以选择在任意一个红苹果之前或之后吃若干个金苹果。我们可以用一个变量 max_gold 来记录当前的金苹果的最大数量。/n/n我们可以使用动态规划来解决这个问题。我们定义一个二维数组 dp，其中 dp[i][j] 表示在前 $i$ 个红苹果中，选择吃苹果的方案中，代码能力为 j 时的最大值。/n/n我们可以使用以下状态转移方程来计算 dp：/n/n- 如果 dp[i-1][j-a[i]] 存在（即代码能力为 j-a[i] 的方案是可行的），那么我们可以选择吃红苹果 $a[i]$，此时的代码能力为 j，即 dp[i][j] = dp[i-1][j-a[i]] + a[i]；/n- 如果 dp[i-1][j] 存在（即代码能力为 j 的方案是可行的），那么我们可以选择不吃红苹果 $a[i]$，此时的代码能力为 j，即 dp[i][j] = dp[i-1][j]。/n/n最终的答案为 dp[n][cur] + max_gold，其中 n 是红苹果的数量，cur 是当前的代码能力，max_gold 是金苹果的最大数量。/n/n下面是实现这个算法的代码：/n/npython/nn, m = map(int, input().split())/na = list(map(int, input().split()))/n/ncur = 1/nmax_gold = 0/n/ndp = [[0] * (cur + 1) for _ in range(n + 1)]/ndp[0][cur] = cur/n/nfor i in range(1, n + 1):/n cur += a[i - 1]/n max_gold = max(max_gold, cur)/n for j in range(cur, 0, -1):/n if dp[i - 1][j - a[i - 1]] > 0:/n dp[i][j] = dp[i - 1][j - a[i - 1]] + a[i - 1]/n if dp[i - 1][j] > 0:/n dp[i][j] = max(dp[i][j], dp[i - 1][j])/n/nanswer = dp[n][cur] + max_gold/nprint(answer)/n/n/n该算法的时间复杂度为 $O(n /cdot m)$，其中 $n$ 是红苹果的数量，$m$ 是金苹果的最大数量。