线上OJ:
一本通:1821:【00NOIP提高组】乘积最大 (opens in a new tab)
AcWing:1026. 乘积最大 (opens in a new tab)
洛谷:P1018 [NOIP2000 提高组] 乘积最大 (opens in a new tab)
核心思想:

1、从上图中可以推出:前i个数 插入j个符号的最大值 = 前k个数(k < i)插入j-1个符号的最大值 * 从第 K+1 ~ 第i个位置组成的数字。即:
2、先计算a[i][j],即表示字符串第i~第j个位置组成的数是多少
举例: 16872的 a[1][3]为168,a[2][4]为687。在dp方程中用得到。
备注 :
在计算 时,; c[j-1] 为输入的第 j 个字符(从c[0]开始)
题解代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, t;
ll a[50][50]; // a[i][j] 表示字符串第i~第j个位置组成的数是多少。举例: 16872的 a[1][3]为168,a[2][4]为687
ll dp[50][7]; // (6<=N<=40,1<=K<=6) dp[i][j]表示前i个数插入j个符号的最大值
char c[50]; // c[i]读入的第i个字符
/*
前i个数插入j个符号的最大值 = 前k个数(k<i)插入j-1个符号的最大值 * 从第 K+1 ~ 第i个位置组成的数字
dp[i][j] = max(dp(i,j), dp[k][j-1] * a[k+1][i] )
*/
int main()
{
// 读入
cin >> n >> t;
for(int i = 0; i < n; i++) cin >> c[i];
// 初始化
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
a[i][j] = a[i][j - 1] * 10 + (c[j - 1] - '0');
for(int i = 1; i <= n; i++)
dp[i][0] = a[1][i]; // 前i个数插入0个乘号时,就是前i个位置组成的数字本身
// dp
for(int i = 1; i <= n; i++) // 穷举前i个数,i不超过n
for(int j = 1; j <= t; j++) // 插入j个乘号,不超过t
for(int k = 1; k < i; k++) // 穷举前k个数,不超过i-1
dp[i][j] = max(dp[i][j], dp[k][j-1] * a[k+1][i]);
printf("%lld", dp[n][t]);
return 0;
}