鏈接
題目描述
給定?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
ChatGPT的題解
題目分析
給定40個正整數，劃分成兩組（均非空），記兩組和為X和S?X，劃分價值為X·(S?X)。由于f(X)=X·(S?X)是關于X的對稱二次函數，在X=S/2處達到最大，因此只需在所有可實現的子集和中，選取最接近S/2的X即可。
解題思路
-
計算總和S；
-
用位運算優化的01背包（bitset）：維護長度為S+1的
dp，dp[i]=1表示存在子集和為i； -
初始
dp[0]=1，對每個數v做dp|=dp<<v； -
從?S/2?向下掃描，找到第一個
dp[x]=1的x，即為最優； -
答案即為1LLx(S?x)。
代碼
#include<bits/stdc++.h>
using namespace std;
int main(){int a[40]={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};int S=0;for(int i=0;i<40;i++)S+=a[i];bitset<226925>dp;dp[0]=1;for(int i=0;i<40;i++)dp|=dp<<a[i];for(int x=S/2;x>=1;x--){if(dp[x]){long long ans=1LL*x*(S-x);cout<<ans;break;}}return 0;
}
復雜度分析
-
時間：O(N·S/word_size)≈40×226924/64≈142000次位運算
-
空間：O(S)≈2.3×10<sup>5</sup>位，約30 KB，完全可行。
