洛谷P1249最大乘积

记录一下从题解里学到的知识点 以下是引用

本题要先用简单的数论和贪心找到最优解的组成方法，再用高精度乘法求积。
以2004为例，由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种，因而一定存在一种分法,使得这些自然数的乘积最大。
若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多，乘积越大。为了使因数个数尽可能地多，我们把2004分成2+3…+n直到和大于等于2004。
若和比2004大1，则因数个数至少减少1个，为了使乘积最大,应去掉最小的2，并将最后一个数（最大）加上1。
若和比2004大k（k≠1）,则去掉等于k的那个数,便可使乘积最大。
例如15：s=2+3+4+5+6刚好大于15，s-15=5，所以把5去掉。
又例如13：s=2+3+4+5刚好大于13，s-13=1,所以去掉2，并把5加1，即3 4 6。

然后没啥好说的了，直接上代码

#include<iostream>
using namespace std;
int a[5005],t=1,result[5005],lenr=5005;
void fenjie(int n)
{
	if(n==3||n==4)
	{
		a[t++]=n;
		return ;
	}
	int s=0;
	for(int i=2;i<=n;i++)
	{
		if(s+i<=n)
		{
			a[t++]=i;
			s+=i;
		}
		else
		{
			a[t++]=i;
			s=s+i-n;
			if(s==1)
			{
				a[1]=0;
				a[t-1]++;
			}
			else
			{
				for(int j=1;j<=i;j++)
				{
					if(a[j]==s)
					{
						a[j]=0;
						break;
					}
				}
			}
			break;
		}
	}
}
void xf()
{
	for(int i=1;i<=t;i++)
	{
		if(!a[i])continue;
		int cur=0;
		for(int j=1;j<=lenr;j++)
		{
			cur=result[j]*a[i]+cur/10;
			result[j]=cur%10;
		}
	}
	while(result[lenr]==0&&lenr>1)lenr--;
}
int main()
{
	int n;
	cin>>n;
	fenjie(n);
	result[1]=1;t--;
	xf();
	for(int i=1;i<=t;i++)
		if(a[i])
			cout<<a[i]<<' ';
	cout<<endl;
	for(int i=lenr;i>=1;i--)
		cout<<result[i];
	cout<<endl;
	return 0;
}