/*
本题可用算法；
1.普通回溯法+HASH
DFS到所有数据（时间复杂度为O(N!)），由于数据规模为250，
较小，完全可以先将所有数据算出后交”表“，交表程序复
杂度为O(1) ，可以AC
2.DP（动态规划）
定义2维数组，记录状态 d[k,x] k为数据大小，x为分量（将
原数分的数的个数，既k=k1+k2+...+kx,d[k,x]记录当前最大
可能.
状态转移: d[k,x]=max{最小公倍数(d[k-1,1],d[1,x-1]),
最小公倍数(d[k-1,2],d[1,x-2]),...最小公倍数(d[k-1,x d
iv 2 +1],d[1,x div 2 -1]),最小公倍数(d[k-2,1],d[2,x-1]
),...,最小公倍数(d[k div 2+1,x div 2 +1],d[k div 2-1,x
div 2 -1]),k}
(1) 记忆化搜索，利用以上规划法优化原普通回溯法，时间复
杂度降低为O(N^3)
(2) 正推递推，利用以上规划法重新实现递推算法，时间复杂
度为 O(N^3)
*/
DP的时间复杂度已经允许直接交纯算法,在很短时间内出解
/*由于本人时间问题，仅实现普通DFS，同时给出其它更好算法（DP
)的思想和转移方程，状态，用此思路完全可以实现.*/
/*算法艺术！
让思维绽放! */
/* BY 卧龙孔明 */
/*时间仓促,提供思想,以下实现程序可能出现小问题,但程序核心算法没有错误*/
#include<stdio.h>
#include<math.h>
#include<conio.h>
/*算法1 普通回溯法（深度优先搜索(DFS))*/
/*
目前信息学竞赛中禁止使用64位长整型变量
因此本程序不使用long long，取而代之使用double(精确17位数)
如果数据规模继续增大，请改为高精度，具体高精度运算程序不提供
*/
double max=0;
int n;
double g(double a,double b)
{
double x=a;
if(a<b)
{
x=b; b=a; a=x;
}
while(fmod(x,b)) x+=a;
return x;
}
int dfs(int left,int c,double now)
{
int i;
if(left>=c)
for(i=c;i<=left;i++) dfs(left-i,i+1,g(now,(double)i));
else
{
if(left!=0) now=g(now,(double)left);
if(now>max) max=now;
return;
}
}
int main(void)
{
int i,j,k;
int flag=0;
int count=0;
scanf("%d",&n);
dfs(n,1,1.0);
printf("%.0lf\n",max);
getch();
return 0;
}
[[it] 本帖最后由 卧龙孔明 于 2008-1-31 08:33 编辑 [/it]]
