省流：高精度，但不是 python
题目传送门
经典 DP。
我们设 \(dp_{i,j}\) 表示前 \(i\) 位用 \(j\) 个乘号的最大值。
边界：\(dp_{i,0}=a_{1,i}\)
转移方程可以考虑对于 \((i,j)\) 枚举乘号的位置 \(k\) 进行转移，于是：
\[dp_{i,j}=\max_{k=j}^{i-1} dp_{k,j-1} \cdot a_{k+1,i}
\]
答案就是 \(dp_{n,m}\)。
但是——这题要装高精度！！
你可以写封装的，我就直接字符串了。
code
#include <bits/stdc++.h>
#define DEBUG
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;constexpr int mod = 998244353;
constexpr int maxn = 45;
constexpr int maxk = 1005;int n, k;
string s;string dp[maxn][maxn], a[maxn][maxn];string init(int l, int r){int pos = l;while (pos < r && s[pos] == '0')pos++;return s.substr(pos, r - pos + 1);
}string max(string x, string y){if (x.empty())return y;if (y.empty())return x;if (x.size() != y.size())if (x.size() > y.size())return x;else return y;else if (x > y)return x;else return y;
}string mul(string x, string y){int lenx = x.size(), leny = y.size(), lenz = x.size() + y.size();string z("");if (x == "0" || y == "0")return "0";int p[maxk], q[maxk], r[maxk];memset(p, 0, sizeof(p));memset(q, 0, sizeof(q));memset(r, 0, sizeof(r));for (int i = 0; i < lenx; i++)p[lenx - i] = x[i] - '0';for (int i = 0; i < leny; i++)q[leny - i] = y[i] - '0';for (int i = 1; i <= lenx; i++)for (int j = 1; j <= leny; j++)r[i + j - 1] += p[i] * q[j];for (int i = 1; i <= lenz; i++)r[i + 1] += r[i] / 10, r[i] %= 10;if (!r[lenz])--lenz;for (int i = lenz; i >= 1; i--)z += (char)(r[i] + '0');return z;
}int main() {fast;cin >> n >> k >> s;s = " " + s;for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)a[i][j] = init(i, j);for (int i = 1; i <= n; i++)dp[i][0] = a[1][i];for (int j = 1; j <= k; j++)for (int i = j + 1; i <= n; i++)for (int t = j; t < i; t++)dp[i][j] = max(dp[i][j], mul(dp[t][j - 1], a[t + 1][i]));cout << dp[n][k];return 0;
}