线上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;
}