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

链接

题目描述

给定 40 个数，请将其任意划分成两组，每组至少一个元素。每组的权值为组内所有元素的和。划分的权值为两组权值的乘积。请问对于以下 40 个数，划分的权值最大为多少。

5160 9191 6410 4657 7492 1531 8854 1253 4520 92311266 4801 3484 4323 5070 1789 2744 5959 9426 44334404 5291 2470 8533 7608 2935 8922 5273 8364 88197374 8077 5336 8495 5602 6553 3548 5267 9150 3309

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

输入输出样例

无

首先注意到有 40 个数，并且只划分成两个部分。

然后发现是背包DP。别问我怎么知道的

可以想到一个 O(全部数之和×40÷2) 的方法（绝对不会TLE），其具体实现是先枚举 40 个数，然后再用背包DP可以生成哪些和，最后再求出这个和×(总和−这个和)就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[41]={-1e9,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},sum,lbj[10000010],num;
long long maxx;
signed main(){ios::sync_with_stdio(0);for(int i=1;i<=40;i++){sum+=a[i];//最大的和就是全部的总和 } bool dp[sum+1];for(int i=1;i<=sum;i++){dp[i]=0;} dp[0]=1;//初始化，啥都不加就是0 for(int i=1;i<=40;i++){for(int j=sum/2;j>=a[i];j--){//枚举到一半即可，因为肯定是一小一大/一半一半 if(dp[j-a[i]]&&!dp[j]){//新的可能值 lbj[++num]=j;dp[j]=1; }}}for(int i=1;i<=num;i++)maxx=max(maxx,1LL*lbj[i]*(sum-lbj[i]));//maxx是long long类型，后面要用1LL乘，因为答案>max intcout<<maxx;
}

其实直接打完表输出就得了，直接输出12873625444