理想汽车大模型笔试0925

选择

代码

题目：数组合并的最大贡献
给定一个整数数组 nums（长度为 n）。你可以重复执行“合并”操作，直到数组被合并成一个数。

合并规则
每次选择两个相邻的连续块 A 和 B 进行合并；
合并的“贡献”定义为这两个块元素之和的乘积：$$\text{contrib}(A,B)=\big(\sum A\big)\times\big(\sum B\big)$$
合并后得到一个新的块，其值为两块元素之和：new_block=∑A+∑B\text{new\_block}=\sum A+\sum Bnew_block=∑A+∑B
继续按照上述规则合并相邻块，直到只剩一个块。



你的任务是：在所有可能的合并顺序中，求总贡献的最大值。总贡献为每一步合并的贡献之和。
输入

第一行一个整数 n，表示数组长度。1 ≤ n ≤ 500
第二行包含 n 个整数，表示数组 nums 的元素。元素取值范围为[1,5000]

输出

一个整数，表示将整个数组合并为一个数时可以获得的最大总贡献。

说明

合并必须发生在相邻的连续块之间。

样例
输入
3
1 2 3
输出
11
解释

先合并 (1) 与 (2)，贡献 1×2=2，形成块 3；再合并 (3) 与 (3)，贡献 3×3=9；总贡献 2+9=11。
或先合并 (2) 与 (3)，贡献 6，形成块 5；再合并 (1) 与 (5)，贡献 5；总贡献 6+5=11。两种顺序的最大总贡献均为 11。

动态规划，比较难，要用到Knuth 优化。普通dp只能20%

没做出来

可能的正确答案：

# 示例输入
# n = int(input().strip())
# a = list(map(int, input().split()))
n = 3
a = [1, 2, 3]

# 前缀和与区间和
prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i + 1] = prefix_sum[i] + a[i]

def seg_sum(l, r):
    return prefix_sum[r + 1] - prefix_sum[l]

# dp[i][j]: 区间 [i, j] 的最大代价
# opt[i][j]: 取得最大代价的最优断点 k
dp = [[0] * n for _ in range(n)]
opt = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = 0
    opt[i][i] = i

# 按长度递增；为使用 opt 的单调性，i 需从大到小遍历
for length in range(2, n + 1):
    for i in range(n - length, -1, -1):  # i: n-length -> 0
        j = i + length - 1
        # Knuth/四边形优化的搜索区间 [l, r]
        l = opt[i][j - 1]
        r = opt[i + 1][j]  # 此时已在本轮前面算过
        # 夹到合法范围 [i, j-1]
        l = max(l, i)
        r = min(r, j - 1)
        best = float("-inf")
        best_k = i
        for k in range(l, r + 1):
            left = dp[i][k]
            right = dp[k + 1][j]
            cost = seg_sum(i, k) * seg_sum(k + 1, j)
            cur = left + right + cost
            if cur > best:
                best = cur
                best_k = k
        dp[i][j] = best
        opt[i][j] = best_k

print(dp[0][n - 1])  # 例子输出 11

第二题没时间看了。