记录编号	69426	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 最优分解方案	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.616 s
提交时间	2013-09-15 14:39:51	内存使用	1.51 MiB

#include<fstream>
#include<cmath>
using namespace std;
ifstream fi("best.in");
ofstream fo("best.out");
int  n;
class high
{
public:
	int num[61];//倒着的存数
	int len;
	high(){for(int i=1;i<=60;i++)num[i]=0;len=1;}
	void output()
	{
		for(int i=len;i>=1;i--)fo<<num[i];
		fo<<endl;
	}
};
bool operator >(high a,high b)
{
	int i;
	if(a.len>b.len)return true;
	if(a.len<b.len)return false;
	i=a.len;
	while(a.num[i]==b.num[i]&&i>0)i--;
	if(i==0)return false;
	if(a.num[i]>b.num[i])return true;
	return false;
}
high operator *(high a,high b)
{
	high c;
	int i,j;
	for(i=1;i<=a.len;i++)
	{
		for(j=1;j<=b.len;j++)
		{
			c.num[i+j-1]+=a.num[i]*b.num[j];
			c.num[i+j]+=c.num[i+j-1]/10;
			c.num[i+j-1]%=10;
		}
		j=i+b.len;
		while(c.num[j]>=10)
		{
			c.num[j+1]+=c.num[j]/10;
			c.num[j]%=10;
			j++;
		}
	}
	i=60;
	while(c.num[i]==0&&i>0)i--;
	c.len=i;
	return c;
}
high exchange(int x)
{
	high ans;
	int k=x,wei=0;
	while(k>0)
	{
		wei++;
		ans.num[wei]=k%10;
		k/=10;
	}
	ans.len=wei;
	return ans;
}
high f[1001];//dp
class boo
{
public:
	bool u[1001];
	void first(){for(int i=1;i<=1000;i++)u[i]=false;}
}used[1001];
int main()
{
	fi>>n;
	/*int i,j,k,tmp=1,imax=1;
	high t,res;
	res=exchange(1);
	while(tmp<=n)
	{
		imax++;
		tmp+=imax;
	}
	tmp=1;
	for(i=2;i<imax;i++)
	{
		t=exchange(1);
		tmp+=i;
		j=0;
		while(tmp+j*i<=n)j++;
		j--;
		//fo<<i<<' '<<j<<endl;
		for(k=1;k<=i;k++)
		{
			t=t*exchange(k+j);
			//t.output();
		}
		if(t>res)res=t;
	}
	res.output();*/
	
	f[1]=exchange(1);used[1].first();used[1].u[1]=true;
	f[2]=exchange(2);used[2].first();used[2].u[2]=true;
	f[3]=exchange(3);used[3].first();used[3].u[3]=true;
	f[4]=exchange(4);used[4].first();used[4].u[4]=true;
	high tmp;
	int i,j,k;
	for(i=5;i<=n;i++)
	{
		used[i].first();
		f[i]=exchange(i);used[i].u[i]=true;
		for(j=2;j<=i-2;j++)
		{
			k=j;
			while(used[i-j].u[k]&&k>0)k--;
			if(k==0)continue;
			tmp=exchange(k)*f[i-j];
			if(tmp>f[i])
			{
				f[i]=tmp;
				used[i]=used[i-j];
				used[i].u[k]=true;
			}
		}
	}
	f[n].output();
	return 0;
}