因为这里涉及到乘号的个数，那么我们可以用f[i][j]表示前i个位乘号为j个时的最大乘积
那么相比上一题就是多了一层枚举多少个乘号的循环，可以得出
f[i][r] = max(f[j - 1][r - 1], num(j, i));
num(j, i)表示第j位到第i位的数，j < i
然后注意要用高精度来计算。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
struct node
{int len, s[MAXN];node() { len = 0; memset(s, 0, sizeof(s)); }
};
int n, k, a[MAXN];
node f[MAXN][10], sum[MAXN][MAXN];node cut(int x, int y)
{node ret;for(int i = y; i >= x; i--)ret.s[++ret.len] = a[i];return ret;
}node cheng(node a, node b)
{node ret;REP(i, 1, a.len + 1)REP(j, 1, b.len + 1){ret.s[i + j - 1] += a.s[i] * b.s[j];ret.s[i + j] += ret.s[i + j - 1] / 10;ret.s[i + j - 1] %= 10;}int& i = ret.len = a.len + b.len - 1;while(ret.s[i+1] > 0){i++;ret.s[i + 1] += ret.s[i] / 10;ret.s[i] %= 10;}while(!ret.s[i] && i > 1) i--;return ret;
}node max_node(node a, node b)
{if(a.len > b.len) return a;else if(a.len < b.len) return b;else{for(int i = a.len; i >= 1; i--){if(a.s[i] > b.s[i]) return a;else if(a.s[i] < b.s[i]) return b;}}return a;
}int main()
{scanf("%d%d", &n, &k);REP(i, 1, n + 1) scanf("%1d", &a[i]), f[i][0] = cut(1, i);REP(i, 1, n + 1)REP(j, i, n + 1)sum[i][j] = cut(i, j);REP(r, 1, k + 1) //乘号的循环在外面 REP(i, 1, n + 1)for(int j = i; j > 1; j--) //这里大于1,边界要注意一下 f[i][r] = max_node(f[i][r], cheng(f[j - 1][r - 1], sum[j][i]));node t = f[n][k];for(int i = t.len; i >= 1; i--) printf("%d", t.s[i]);puts("");return 0;
}