codevs 2612 最有分解方案 （贪心）

/* 数字不重复 将一个正整数分解成若干的整数的和 数字不重复 且数字不相同 保证不重复的话 贪心策略是从2开始分 然后把最后剩下的数均匀分到后面 证明嘛 这里写的可能不是很严谨 对于一个n 如果我们先分解成了两个a1 a2 我们设 x为a2-a1 若x>=3显然我们把x拿出来 即变成 x a1 a2-x 这样会更优 然后我们要保证不重复 从2开始拆 每次+1 把剩下的给后面的每个+1 这样一定不会重复 而且满足我们刚才的最优策略 然后写个高精乘单精 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 2600 using namespace std; int n,ans[maxn],l,p[maxn]; void Mul(int x) {for(int i=1;i<=l;i++)ans[i]=ans[i]*x;for(int i=1;i<=l;i++)if(ans[i]>9){ans[i+1]+=ans[i]/10;ans[i]=ans[i]%10;}while(ans[l+1]){l++;ans[l+1]+=ans[l]/10;ans[l]=ans[l]%10;} } int main() {scanf("%d",&n);int i,k,s=0;for(i=2;i;i++){if(n-i<0)break;n=n-i;p[++s]=i;}k=n;while(k)for(int i=s;i>=1;i--)if(k){p[i]++;k--;}ans[1]=1;l=1;for(int i=1;i<=s;i++)Mul(p[i]);for(int i=l;i>=1;i--)printf("%d",ans[i]);return 0; }

 

转载于:https://www.cnblogs.com/yanlifneg/p/5551249.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的codevs 2612 最有分解方案 （贪心）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。