Description
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样
一道题目:
设有一个长度N的数字串，要求选手将它分成K个部分，找出一种分法，使得这K个部分的乘积能够为最大
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串: 312，当N=3，K=2时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
Input
输入文件只有一行包含3个用空格分开的整数分别是 N，K和 N位整数。
Output
一个整数，表示讲n分成K个部分的最大乘积。
Sample Input
5 3 12345
Sample Output
2460
Hint
【样例说明】
将 12345分成 3部分，由下面6种分法：
1*2*345=690
1*23*45=1036
1*234*4=936
12*3*45=1620
12*34*5=2040
123*4*5=2460
有上面可以看出，最大乘积是最后一种分法，所以最大值是 2460
【数据范围】：
N <=100; k<=N
【参考程序】：
#include<cstring>
#include<cstdio>
using namespace std;
typedef int arr[110];
arr F[110][110],sum[110][110];
char s[110];
int n,k;
void getsum(int x,int y)
{
memset(sum[x][y],0,sizeof(sum[x][y]));
sum[x][y][0]=y-x+1;
int len=y-x+1;
for (int i=1;i<=len;i++)
sum[x][y][i]=s[y-i]-'0';
}
void mul(arr a, arr b,arr &sum2)
{
memset(sum2,0,sizeof(sum2));
sum2[0]=a[0]+b[0]-1;
for (int i=1;i<=a[0];i++)
for (int j=1;j<=b[0];j++)
sum2[i+j-1]+=a[i]*b[j];
for (int i=1;i<=sum2[0];i++)
{
sum2[i+1]+=sum2[i]/10;
sum2[i]%=10;
}
while (sum2[sum2[0]+1])
{
sum2[0]++;
sum2[sum2[0]+1]+=sum2[sum2[0]]/10;
sum2[sum2[0]]%=10;
}
}
bool check(arr a,arr b)
{
if (a[0]<b[0]) return true;
if (a[0]>b[0]) return false;
for (int i=a[0];i>=1;i--)
if (a[i]<b[i]) return true;
else if (a[i]>b[i]) return false;
return false;
}
int main()
{
scanf("%d%d%s",&n,&k,s);
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
getsum(i,j);
for (int i=0;i<=n;i++)
for (int j=0;j<=k;j++)
F[i][j][0]=F[i][j][1]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
for (int l=j;l<=i;l++)
{
arr sum2;
mul(F[l-1][j-1],sum[l][i],sum2);
if (check(F[i][j],sum2))
memcpy(F[i][j],sum2,sizeof(F[i][j]));
}
int len=F[n][k][0];
printf("%d",F[n][k][len]);
for (int i=len-1;i>=1;i--) printf("%d",F[n][k][i]);
printf("\n");
return 0;
}