分析： 这一题虽然是加强版的，但也就是数据范围比原题大了点儿，思路都一样，在原题的基础上加一个高精度乘法就OK了，下面说一下算法：看到题首先想到的就是动态规划，你会发现这一题极像一道经典题目———添加号问题，只不过那个是加法。

设F[i][j]表示前j个数中加入i个乘号的最大值，则有状态转移方程：

F[i][j]=MAX(F[i-1][k]*Num[k 1][j])(i<=k<j)

F[i-1][k]表示在第k个数之前添加i-1个乘号的最大值，Num[k 1][j]表示从第k 1个数开始到第j个数截止，这一串数字的数值。

附上程序：

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int a[41],F[7][41][41],Temp[41],n,m,Num[41][41][41];

void Init()

{

    int i,j,t,k;

    freopen("1007.in","r",stdin);

    freopen("1007.out","w",stdout);

    scanf("%d %d\n",&n,&m);

    for (i=1;i<=n;i )

    {

        scanf("%c",&a[i]);

        a[i]-='0';

    }

    for (i=1;i<=n;i )//生成第i个数到第j个数这一串数字代表的数值

      for (j=i;j<=n;j )

      {

        t=0;

        for (k=i;k<=j;k )

        {

          Num[i][j][ t]=a[k];

        }

        Num[i][j][0]=t;

      }

    for (i=1;i<=n;i )//给F数组初始化

    {

      memcpy(F[0][i],Num[1][i],sizeof(Num[1][i]));

      for (j=1;j<=F[0][i][0]/2;j )

        swap(F[0][i][j],F[0][i][F[0][i][0] 1-j]);

    }

}

void gjd(int (&x)[41],int (&y)[41])//高精度乘法

{

    int i,j,a[41],b[41];

    memcpy(a,x,sizeof(x));

    memcpy(b,y,sizeof(y));

    memset(Temp,0,sizeof(Temp));

    for (i=1;i<=b[0]/2;i )

      swap(b[i],b[b[0] 1-i]);

    for (i=1;i<=a[0];i )

        for (j=1;j<=b[0];j )

        {

            Temp[i j-1] =a[i]*b[j];

            Temp[i j] =Temp[i j-1]/10;

            Temp[i j-1]%=10;

        }

    if (Temp[a[0] b[0]]>0)

        Temp[0]=a[0] b[0];

    else

        Temp[0]=a[0] b[0]-1;

}

int Min(int (&a)[41],int (&b)[41])//求两者中较小的一个

{

    if (a[0]<b[0])

        return 1;

    if (a[0]>b[0])

        return 0;

    for (int i=a[0];i>0;i--)

        if (b[i]>a[i])

            return 1;

        else if (b[i]<a[i])

            return 0;

    return 0;

}

void Dynamic()//DP过程

{

    int i,j,k;

    for (i=1;i<=m;i )

        for (j=2;j<=n;j )

            for (k=i;k<j;k )

            {

                gjd(F[i-1][k],Num[k 1][j]);//算出当前方案的值

                if (Min(F[i][j],Temp))

                    memcpy(F[i][j],Temp,sizeof(Temp));//更新最优值

            }

}

void Print()//打印

{

    for (int i=F[m][n][0];i>0;i--)

        printf("%d",F[m][n][i]);

    printf("\n");

    fclose(stdin);

    fclose(stdout);

}

int main()

{

    Init();

    Dynamic();

    Print();

    return 0;

}

小结：

   这一题程序写的有些乱，很繁琐，很久没编高精度乘法了，都快忘了，这次影响我的主要原因是在函数中传递数组，这个东西很不熟，导致我调了半天，我以后要注意C 中的一些小细节，才能保证我在竞赛中最大程度的发挥自己的能力。