http://acm.pku.edu.cn/JudgeOnline/problem?id=1032給出n，把n分解為若干不相同數(shù)之和，使之乘積最大。
貪心，Discuss里面的思路：把n分解為從2開始的連續(xù)整數(shù)，如果有多，則從高位開始依次加1。如26，我們得到2+3+4+5+6，此時(shí)還剩余6（26-2-3-4-5-6），接下來從高位依次加一，變成3+4+5+6+7，還剩1，繼續(xù)加給最大的7，最后答案是3+4+5+6+8.
#include<iostream>
using namespace std;
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=2;i<=n;i++)
n-=i;
i--;
if(i==n)
{
for(j=2;j<i;j++)
printf("%d ",j+1);
printf("%d\n",i+2);
}
else
{
if(n==0)
{
for(j=2;j<i;j++)
printf("%d ",j);
printf("%d\n",i);
continue;
}
for(j=2;j<i;j++)
{
if(i-j<n)
printf("%d ",j+1);
else
printf("%d ",j);
}
printf("%d\n",i+1);
}
}
return 0;
}FZU1698 最大乘積 各種CE+PE+WA 無數(shù)次，終于不PE了。但不懂PE哪里了。
要求輸出分解的數(shù)(不同)
http://acm.fzu.edu.cn/problem.php?pid=1698AC code
import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class Main
{
public static void main(String[] args)
{
int n;
Scanner cin=new Scanner(System.in);
while(cin.hasNextInt())
{
n=cin.nextInt();
if(n<3)
continue;
if(n==3)
{
System.out.println("1 2");
System.out.println("2");
}
else if(n==4)
{
System.out.println("1 3");
System.out.println("3");
}
else if(n>=5&&n<10000)
{
int i;
BigInteger res=BigInteger.valueOf(1);
for(i=2;i<=n;i++) n-=i;
i--;
if(n==0)
{
for(int j=2;j<i;j++)
{
System.out.print(j+" ");
res=res.multiply(BigInteger.valueOf(j));
}
System.out.println(i);
res=res.multiply(BigInteger.valueOf(i));
}
else if(i==n)
{
for(int j=2;j<n;j++)
{
System.out.print((j+1)+" ");
res=res.multiply(BigInteger.valueOf((j+1)));
}
System.out.println(i+2);
res=res.multiply(BigInteger.valueOf((i+2)));
}
else
{
for(int j=2;j<i;j++)
{
if(i-j<n)
{
System.out.print((j+1)+" ");
res=res.multiply(BigInteger.valueOf((j+1)));
}
else
{
System.out.print(j+" ");
res=res.multiply(BigInteger.valueOf(j));
}
}
System.out.println(i+1);
res=res.multiply(BigInteger.valueOf(i+1));
}
System.out.println(res);
}
}
}
}
求一個(gè)數(shù)分解式的最大乘積(可以相同)。
對(duì)任意一個(gè)正整數(shù)x>3,令i=x/3,j=x%3，設(shè)S為分解式乘積最大的數(shù) 。
當(dāng) j=0 時(shí) s=3的i次方
當(dāng) j=1 時(shí) s=3的(i-1)次方*4
當(dāng) j=2 時(shí) s=3的i次方*2
練習(xí)：FOJ1823 Lou 1 Zhuang
http://acm.fzu.edu.cn/problem.php?pid=1823