题解：P12207 [蓝桥杯 2023 国 Python B] 划分
_Ec__yt_qwq_
·
·
题解
思路
01 背包模版变形。
下面就是本题的思路了（较详细）：
准备工作：首先将这 40 个数存储到 a 数组中，随后将它们求和存储为 sum，dp_0 \gets 0。
由于我们只有选和不选两种选择，所以使用 bool 类型存储数组比较合适。
外层循环遍历这 40 个数，内层循环从 \frac{sum}{2} 遍历到当前外层循环遍历到的数 a_i（不包含 a_i）。
推导公式：dp_i \gets dp_{i-a_i}。通过遍历每个数，更新可能达到的和。
随后我们可以寻找最优解。从 \frac{sum}{2} 开始，向下查找最大的可行和，并计算对应的乘积。
代码
```cpp
#include <iostream>
using namespace std;
int a[]={5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231, 1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309};
long long sum,mx;
bool dp[1000005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(int i:a)sum+=i;
sum/=2;
dp[0]=1;
for(int k:a){
for(int i=sum;i>=k-1;i--){
if(dp[i-k])dp[i]=1;
}
}
for(int i=sum;i>=0;i--)if(dp[i]){mx=i;break;}
long long p=mx*(sum*2-mx);
cout<<p;
return 0;
}
```
$\texttt{Py}$：
```py
a = [
5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231,
1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,
4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,
7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309
]
t = sum(a)
h = t // 2
dp = [0] * (h + 1)
dp[0] = 1
for k in a:
for i in range(h, k - 1, -1):
if dp[i - k]:
dp[i] = 1
m = 0
for i in range(h, -1, -1):
if dp[i]:
m = i
break
r = m * (t - m)
print(r)
```