最优分解问题
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。
输入
第1行是正整数n。（n不超过50）
输出
计算出的最大乘积。
样例输入 Copy
10
样例输出 Copy
30
具体证明：传送门
贪心的思想，和一定时，如果两个数差值越小，乘积就越大（好像是个数学公式？）
所以从2开始枚举，累加和为sum，直到sum+i>n时停止
可能会有剩下的值，从后向前依次将该数加1即可。
重点是特判
当n=1时，可以拆成1和0，答案为0。
当n=2时，只能拆成2和0，答案为0。
因为要求拆出来的正整数不相同，所以1和1不可行
当n=3时，可以拆成1和2，答案为2。
当n>=4时，开始枚举即可。
坑点就是n=2。。
#include<bits/stdc++.h> typedef long long ll; using namespace std; int main(){ int n;cin>>n; if(n<=4){ if(n==2) cout<<0<<endl; else cout<<max(n-1,0)<<endl; return 0; } vector<int>v; int sum=0; for(int i=2;i<=n;i++){ if(sum+i<=n) v.push_back(i),sum+=i; else break; } int tmp=n-sum; ll res=1; /// cout<<tmp<<endl; /// cout<<v.size()<<endl; for(int i=v.size()-1;i>=0;i--){ if(tmp>0) v[i]++,tmp--; else break; } int ans=0; for(auto tt:v){ ///cout<<tt<<" "; res*=tt; ans+=tt; } cout<<res<<endl; /// cout<<ans<<endl; return 0; }
补来自学长的证明：
a+b=c
b=c-a
ab=(c-a)a=ac-aa
对称轴 a=c/2
根据一元二次方程a取 对称轴左右时最大
从而将问题从两个数转换到三个数
至多个数
