1249 最大乘积

乘积"/>

1249 最大乘积

1249 最大乘积

很明显这是一个贪心，把一个数字拆成和，使得他们的乘积最大
我还以为是动态规划呢
还有就是，高精度也是比较恶心的
首先，先找找规律
3…1 2
4…2 2
5…2 3
6…2 4
7…3 4
8…3 5
9…2 3 4
有不有发现了啥子规律
是的！
每一个数都成小到大的排序了
所以说，我们用贪心从2开始递增的累加，知道加到n，再用高精度撑起来就好了
好简（bian）单（tai）

#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;
long long n,x=0,sum=0,ss=1,i=2,t=1;
int a[10001];
int s[10001];
void jc(int x)
{for(int i=1;i<=t;i++){s[i]=s[i]*x;}for(int i=1;i<=t;i++){if(s[i]>=10){long long add=s[i]/10;s[i+1]+=add;s[i]=s[i]%10;if(i+1>t)t=i+1;}}
}
int main()
{s[1]=1;cin>>n;//10while(sum<n){a[++x]=i;//1 2 3 4sum+=i;//1 3 6 10i++;//2 3 4 5}a[sum-n-1]=0;for(int i=1;i<=x;i++){if(a[i]!=0)cout<<a[i]<<' ';if(a[i]!=0)jc(a[i]);//计算乘积 }cout<<endl;for(int i=t;i>=1;i--)cout<<s[i];cout<<endl;return 0;
}