3737 - 贵州大学第五届程序设计竞赛 整数分解
时间限制 : 1 秒
内存限制 : 128 MB
给定一个正整数N，可以分解成若干个正整数之和，求各种分解得到的整数最大可能的乘积。例如5可以分解成5=5，5=1+4，5=2+3，5=1+1+3，5=1+2+2，5=1+1+1+2，5=1+1+1+1+1，其中2*3=6是分解得到的数乘积最大的。
题目输入
输入包括多组测试数据。每组测试数据一行，包含一个待分解的正整数N(0<=N<=1000)。N为0表示输入结束。
题目输出
对每组测试数据，输出对应分解得到的最大乘积。
输入/输出样例
输入格式
5 6 0
输出格式
6 9
C++解答
#include <stdio.h> #include <algorithm> #include <stack> #include <queue> #include <map> #include <string.h> using namespace std; int dp[1005]; int max(int a,int b) { if(a>b) return a; else return b; } int main() { dp[1]=1; dp[2]=2; dp[3]=3; dp[4]=4; dp[5]=6; int i,j; int maxa=-1; for( i=6;i<=1000;i++) for( j=1;j<i;j++) { maxa=max(maxa,dp[j]*(i-j)); dp[i]=maxa; } int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; printf("%d\n",dp[n]); } return 0; }