设n是一个正整数。现要求将n分解为若干个自然数的和，且使这些自然数的乘积最大。
对于给定的正整数n，编程计算最优分解方案。

# include<iostream>
using namespace std;
int main()
{
int n,m,i,j,h,d;double s=1,s1=1,k=1,max=1;double a[10000];
cin>>n;
i=1;
if(n==1)cout<<0;
else if(n==2)cout<<1;
else if(n==3)cout<<2;
else
{
while(i<=n/2)
{
m=n/i;
s=1;
k=1;
for(j=1;j<=m;j++)
s=s*i;
d=n%i;
if(d==0)s1=s;/*把数用除来分解*/
else
{
for(j=1;j<=d;j++)
{k=(s/i)*(i+1);
s=k;
}
s1=k;
}
a[i-1]=s1;
i++;

}
for(i=0;i<n/2;i++)
{ if(a[i]>=max)
{ max=a[i];
h=i;}
}
cout<<h<<" ";
cout<<max;
}
return 0;
}
不知道有没有更好的算法!这个代码是错的!~不知道错在那??????

不错的DP题，应该是O(n^3)，不过输入的n不可能很大（如1000的结果就很巨大了）
所以n^3也问题不大



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-17 16:17:26编辑过]

see nku 1116

http://acm.nankai.edu.cn/p1116.html


I did this problem a few months ago and figured out you only need to consider writing

n as a sum of 2 and 3's.

Try your best and submit your code to the online judge. If you cannot pass, i will post my work tomorrow.

It is bed time now.

[此贴子已经被作者于2007-9-17 17:16:39编辑过]

------------------------
4 5 6
2 2 2 3 2 3

7 8 9
3 4 2 6 3 6

偶习惯用DP来想问题了。。。不过DP也菜。。。
可以找出的规律是弄出尽可能多的因子3，余1的话就少拆一个3转换为一个4


by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-17 17:22:22编辑过]

基于飞燕MM的思想，我弄了这个程序，不过超时了。等会儿吃完饭优化一下速度看
[CODE]#include <stdio.h>
#include <math.h>
int main()
{
int a,b,c,p;
while(scanf("%d",&a))
{
if(a<=0) break;
b=a/3;
c=a%3;
switch(c)
{
case 0:
p=int(pow(3,b));
break;
case 1:
p=int(pow(3,b-1)*4);
break;
case 2:
p=int(pow(3,b)*2);
break;
}
printf("%d\n",p);
}
return 0;
}[/CODE]

不超时才怪，死循环一个



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

我用VC6输入0时就退出循环了，难道VC6不行

你试过真的？？？我不信
你看看题目说的什么结束程序



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

here is my submitted code at nku.

I implemented a BigInt * BigInt method inside --- which is not efficient. You may want to rewrite it in either C or asm.

The basic idea is as follows. Let q = n/3, r = n%3.

If r==0, then max product = 3^q;
If r==1, then max product = 3^(q-1)*4;
If r==2, then max product = 3^q * 2.

char a[10002];

void f(int k)
{
    int i=1, m=1, c, t, j;
    a[0]='1';
    for(j=1; j<=k; ++j)
    {
        c=0;
        for(i=0; i<m; ++i)
        {
            t = 3*(a[i]-'0')+c;
            a[i] = '0'+t%10;
            c = t/10;
        }
        if(c>0)
        {
            a[i]='0'+c;
            ++i;
            ++m;
        }
    }
    a[i]='\0';
}
void g(int k)
{
    int i, m, c, t;
    m=strlen(a);
    c=0;
    for(i=0; i<m; ++i)
    {
        t = k*(a[i]-'0')+c;
        a[i] = '0'+t%10;
        c = t/10;
    }
    if(c>0)
    {
        a[i]='0'+c;
        ++i;
        ++m;
    }
    a[i]='\0';
}
main()
{
    int n, q, r;
    char*b, *e, ch;
    while(scanf(\"%d\", &n)!=-1)
    {
        if(n<4)
        {
            printf(\"%d\n\", n);
            continue;
        }
        q=n/3;
        r=n%3;
        if(r==0)
            f(q);
        else if(r==1)
        {
            f(q-1);
            g(4);    
        }
        else
        {
            f(q);
            g(2);            
        }
        b = a;
        e = a+strlen(a)-1;
        while(b<e)
        {
            ch=*b;
            *b++=*e;
            *e--=ch;
        }
        printf(\"%s\n\", a);
        a[0]='\0';
    }
}

我晕难道南开的服务器是网通的??这会进N次进不去了
TO:雨中飞燕
不试过我怎么会乱说话呢?