乘积最大

【题目描述】

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

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

(1)3*12=36；

(2)31*2=62；

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

【输入描述】

程序的输入共有两行。

第一行共有2个自然数N、K(6 ≤ N ≤ 40，1 ≤ K ≤ 6)；

第二行是一个长度为N的数字串。

【输出描述】

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

【样例输入】

4 2

1231

【样例输出】

62

源代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,k,f[41][41]={0},sum[41][41]={0};
string s;
int main()
{
    scanf("%d%d",&n,&k);
    cin>>s;
    s=" "+s;
    for (int a=1;a<=n;a++) //起点。
      for (int b=a;b<=n;b++) //终点。
      {
          int t=b-a;
          for (int c=0;c<t;c++)
          {
            long long v=1;
            for (int d=0;d<t-c;d++)
              v*=10;
            sum[a][b]+=v*(s[a+c]-48);
          }
          sum[a][b]+=s[b]-48;
      } //求各个区间数。
    for (int a=1;a<=n;a++) //没有乘号的数都是原数。
      f[a][0]=sum[1][a];
    for (int b=1;b<=k;b++) //枚举乘号数量。
      for (int a=2;a<=n;a++) //枚举第几位数字。
        for (int c=1;c<a;c++) //枚举乘号位置求最大值。
            f[a][b]=f[a][b]>f[c][b-1]*sum[c+1][a]?f[a][b]:f[c][b-1]*sum[c+1][a]; //分区间法。
    printf("%d",f[n][k]);
    return 0;
}