题目描述

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
1) 3*12=36
2) 31*2=62
这时，符合题目要求的结果是：31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入描述:

第一行共有2个自然数N，K（6 ≤ N ≤ 40，1 ≤ K ≤ 6）
第二行是一个长度为N的数字串。

输出描述:

输出所求得的最大乘积（一个自然数）。

示例1

输入
4 2
1231
输出
62

解答

表示前 个数字中含有j个乘号时的最大值，则有： 

#include<cstdio>
#include<cstring>
using namespace std;
 
const int maxn=40;
int n,m,a[maxn+20],b[maxn+20],c[maxn+20];
int f[maxn+20][10][maxn+20];
 
void multi(int d[],int p[],int q[])
{
  int i,j,k,last=0;
  d[0]=p[0]+q[0]-1;
  for(k=1;k<=d[0];k++)
    {
      for(d[k]=last,i=1;i<=p[0];i++)
        if(k+1-i>=1 && k+1-i<=q[0])d[k]+=p[i]*q[k+1-i];
      last=d[k]/10,d[k]%=10;
	} 
  if(last>0)d[++d[0]]=last;
}
 
void MAX(int p[],int q[])
{
  int i;
  if(p[0]>q[0])return;
  if(p[0]==q[0])
    {
      for(i=p[0];i>=1;i--)
        {
          if(p[i]>q[i])return;
          if(p[i]<q[i])break;
		}
	  if(i<1)return;
	}
  for(i=0;i<=q[0];i++)p[i]=q[i];
}
 
int main()
{
  int i,j,k,x;  
  scanf("%d%d\n",&n,&m);
  for(i=1;i<=n;i++)a[i]=getchar()-'0';
  for(i=1;i<=n;i++)
    for(f[i][0][0]=i,j=1;j<=i;j++)
      f[i][0][j]=a[i+1-j];
      
  for(k=1;k<=m;k++)
    for(i=k+1;i<=n;i++)
      for(j=k;j<i;j++)
        {
          for(b[0]=0,x=i;x>j;x--)b[++b[0]]=a[x];
          multi(c,f[j][k-1],b);
          MAX(f[i][k],c);
		}
  for(i=f[n][m][0];i>=1;i--)printf("%d",f[n][m][i]);
  return 0; 
}



来源：yuyanggo