题解：P12207 [蓝桥杯 2023 国 Python B] 划分

l15130880055 · 2025-04-18 19:59:08 · 题解

P12207 [蓝桥杯 2023 国 Python B] 划分

Problem

给你 40 个数，随便划分成两组，使得各组元素和之积最大。

Solution

根据基本不等式，为了让各组元素和之积最大，那么各组的和越接近就是越优的，于是转化成了一个背包 dp 问题。

令 dp_i 表示能不能使一组的和为 i，转移和正常背包一样。令 a 表示 40 个数之和，然后从 \frac{a}{2} 开始到 0 找到一个最接近 \frac{a}{2} 的和，设它为 b。

我们要求的答案就是 b(a-b)。

最后经笔者这边跑出来答案就是 12873625444。

Code

代码不贴了，注意复制完题目中的数组下标从 0 开始，有需要的可以私信我。