noip2000乘积最大 （高精度，动态规划）

A1125. 乘积最大

1.0s 内存限制： 256.0MB

​​355​​ AC次数： 182 平均分： 65.49

将本题分享到：

​​查看未格式化的试题​​​ ​​​提交​​​ ​​​试题讨论​​

试题来源

　　NOIP2000 提高组

问题描述

　　今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

　　设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

　　同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

　　有一个数字串：312， 当N=3，K=1时会有以下两种分法：

　　3*12=36
　　31*2=62

　　这时，符合题目要求的结果是：31*2=62

　　现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入格式

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

输出格式

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

样例输入

4 2
1231

样例输出

62

解析：f[i][j]表示前 i 个数字中含有 j 个乘号时的最大值，则有：

f[i][j]=max{f[k][j-1]*num(k+1,i)，j<=k<i}

代码：

#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; 
}