洛谷题目：P1018 [NOIP 2000 提高组] 乘积最大题解

题目传送门：

P1018 [NOIP 2000 提高组] 乘积最大 - 洛谷 (luogu.com.cn)

前言：

本题可以使用DP来解决。动态规划的核心思想是将一个复杂的问题分解为多个简单的子问题，并通过求解子问题的最优解来得到原问题的最优解。在本题中，我们通过逐步增加乘号的数量和数字串的长度，利用之前计算出的子问题的最优解来计算当前问题的最优解。已下是题目具体实现步骤：

#步骤：

1、状态定义：

设 dp[i][j] 表示在前 $i$ 个数字当中插入 $j$ 个乘号所能得到的最大乘积。这里的 $i$ 的范围是从到 1 到 $N$ ， $j$ 的范围是从 0 到 $k$ 。

2、边界条件：

当没有乘号时, dp[i][0] 就是前 $i$ 个数字组成的整数。例如，对于数字串 123， dp[2][0] 就是数字 12。

3、状态转移方程：

对于 dp[i][j] ，我们需要枚举最后一个乘号插入的位置 $k(j<k<i)$ 。插入最后一个乘号后，数字串被分成两个部分：前 $k$ 个数字中插入了 $j-1$ 个乘号，以及第 $K+1$ 个数字到第 $i$ 个数字组成的整数。

因此，状态转移方程公式为：

$dp[i][j]=max_{j<k<i} dp([k][j-1]\times num(k+1,i))$

其中，num(k+1,i) 表示从第 $k+1$ 数字到第 $i$ 个数字组成的整数。

4、高精度计算：

由于最终结果可能非常大，超出了普通整数类型（如 int、long long）的表示范围，所以需要使用高精度计算。在代码中，我们使用 vector<int> 来存储高精度数，每个元素代表一位数字，并且低位在前，高位在后。同时，实现了高精度乘法函数 multiply 来进行乘法运算，以及比较函数 isGreater 来比较两个高精度数的大小。

5、最终结果：

最终答案存储在 $dp[N][K]$ 中，即在前 $N$ 个数字中插入 $K$ 个乘号所能获得的最大乘积。

##复杂度分析：

1、时间复杂度：

由于有三层嵌套循环，每层循环的时间复杂度分别为 $K$ 和 $N$ 和 $N$ 相关，并且高精度乘法的时间复杂度与数字程度的平方成正比，所以总的时间复杂度为 $O(K\times N^{2} \times M^{2} )$ ，其中 $M$ 是高精度数的最大长度。

2、空间复杂度：

主要用于 dp 数组，其大小为 $N \times K \times M$ ，所以总的空间复杂度为 $O(N\times K\times M)$ 。

###代码：

#include <bits/stdc++.h>
using namespace std;
vector<int> m(const vector<int>& a, const vector<int>& b) {vector<int> res(a.size() + b.size());for (int i = 0; i < a.size(); ++i) {for (int j = 0; j < b.size(); ++j) {res[i + j] += a[i] * b[j];res[i + j + 1] += res[i + j] / 10;res[i + j] %= 10;}}while (res.size() > 1 && res.back() == 0) res.pop_back();return res;
}
bool G(const vector<int>& a, const vector<int>& b) {if (a.size() != b.size()) return a.size() > b.size();for (int i = a.size() - 1; i >= 0; --i) {if (a[i] != b[i]) return a[i] > b[i];}return false;
}
vector<int> S(const string& s) {vector<int> num;for (int i = s.size() - 1; i >= 0; --i) {num.push_back(s[i] - '0');}return num;
}
void P(const vector<int>& num) {for (int i = num.size() - 1; i >= 0; --i) {cout << num[i];}cout << endl;
}
int main() {int n, k;cin >> n >> k;string ns;cin >> ns;vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1));for (int i = 1; i <= n; ++i) {dp[i][0] = S(ns.substr(0, i));}for (int j = 1; j <= k; ++j) { for (int i = j + 1; i <= n; ++i) {  for (int l = j; l < i; ++l) {  vector<int> product = m(dp[l][j - 1], S(ns.substr(l, i - l)));if (G(product, dp[i][j])) {dp[i][j] = product;}}}}P(dp[n][k]);return 0;
}