题解：P1018 [NOIP2000 提高组] 乘积最大
kuaiCreator
·
·
题解
题目大意
将一串长度为 n 的数字字符串，分成 k+1 个整数，使这 k+1 个整数的乘积最大。
本题是划分型动态规划的经典例题。
划分型动态规划通常是将 n 个元素划分为无限组或有限组同时计算分成若干组的最优解或方案数等问题。
状态定义一般为 f(i,j) 表示把前 i 个元素分为 j 组时的最优状态。
解题思路
特别注意：由于读入的字符串长度 N\le 40 计算结果很大需要开高精度。
1、定义状态
#### 2、分解子问题
$$f(i,j)=\max\limits_{k=j}^{i-1}f(k,j-1)\times num(k+1,i)$$
$num(k+1,i)$ 表示由字符串的第 $k+1$ 至 $i$ 位组成的数。
#### 3、初始化状态和边界状态
问题状态初始化：
$$f(l,r) = 0 \quad l,r∈[1..n]$$
边界状态初始化：
$$f(0,j) = 0,f(i,0) = num(1 , i)\quad i,j∈[1..n]$$
#### 4、计算顺序
第一层循环枚举前 $i$ 个数从 $1$ 到 $n$。
第二层循环枚举插入乘号的数量 $j$ 从 $1$ 到 $\min(m,i-1)$。
第三层循环 $k$ 枚举插入的位置 $j$ 到 $i-1$。
#### 5、最终答案
$$ans=f(n,m)$$
#### 6、效率分析
时间复杂度 $O(n^2m)$。
空间复杂度 $O(nm)$。
## 代码展示
为方便理解附上一个不带高精度的代码。带高精度的写法建议用类类型或者结构体并重载运算符实现。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 50;
long long dp[N][N], n, m, num[N][N]; //long long 可以替换为高精度类型
string str;
int main() {
cin >> n >> m >> str;
str = ' ' + str; //让字符串有用的信息从下标 1 开始
for (int i = 1; i <= n; i++) //把字符串第i至第j个位置的子串转换为整数
for (int j = i; j <= n; j++)
num[i][j] = num[i][j - 1] * 10 + str[j] - '0';
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) //初始化边界状态
dp[i][0] = num[1][i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) { //j<i表示i个数最多插入i-1个乘号
if (j >= i) break; //前i个元素不能被插入j个隔板分成j+1份
for (int k = j; k < i; k++) //前k个元素最多插入j-1个符号故k从j开始枚举
dp[i][j] = max(dp[i][j], dp[k][j - 1] * num[k + 1][i]);
}
cout << dp[n][m];
return 0;
}
```
满分代码
```cpp
#include <bits/stdc++.h>
using namespace std;
class BINT { //类类型，这里可以替换成struct
private: //私有成员
string s;
public: //公有成员
BINT(string x = "0"): s(x) {}; //初始化构造函数
const BINT operator+(const BINT &t) { //重载加法运算
string sa = s, sb = t.s;
int la = sa.size(), lb = sb.size();
int m = max(la, lb); //获得最大数字长度
vector<int> a(m + 1, 0), b(m + 1, 0), c(m + 1, 0);
for (int i = 0; i < la; i++) //逆序存数a
a[i] = sa[la - 1 - i] - '0';
for (int i = 0; i < lb; i++) //同上
b[i] = sb[lb - 1 - i] - '0';
for (int i = 0; i < m; i++) {
c[i] += a[i] + b[i]; //对位相加
c[i + 1] += c[i] / 10; //处理进位
c[i] = c[i] % 10; //去掉进位
}
while (!c[m] && m) m--; //去除前导零
string res;
for (int i = m; i >= 0; i--)
res += char(c[i] + '0');
return BINT(res); //临时BINT类型
}
const BINT operator*(const BINT &t) {
string sa = s, sb = t.s;
int la = sa.size(), lb = sb.size();
int m = la + lb;
vector<int>a(m + 1, 0), b(m + 1, 0), c(m + 1, 0);
for (int i = 0; i < la; i++) //逆序存数
a[i] = sa[la - 1 - i] - '0';
for (int i = 0; i < lb; i++)
b[i] = sb[lb - 1 - i] - '0';
for (int i = 0; i < la; i++)
for (int j = 0; j < lb; j++) {
c[i + j] += a[i] * b[j];
c[i + j + 1] += c[i + j] / 10;
c[i + j] %= 10;
}
while (!c[m] && m) m--;
string res;
for (int i = m; i >= 0; i--)
res += char(c[i] + '0');
return BINT(res);
}
bool operator<(const BINT &t) {
string b = t.s;
if (s.size() < b.size()) return true;
if (s.size() == b.size() && s < b) return true;
return false;
}
void operator=(const string &x) { //重载赋值运算符
s = x;
}
void operator=(const long long &x) { //重载赋值运算符
s = to_string(x);
}
void operator=(const int &x) { //重载赋值运算符
s = to_string(x);
}
friend istream& operator>>(istream & in, BINT & t) {
in >> t.s; //友元函数 重载>>右移运算符为输入
return in;
}
friend ostream& operator<<(ostream & out, const BINT & t) {
out << t.s; //友元函数 重载 <<左移运算符为输出
return out; //const允许输出常量
}
};
int n, m;
string s;
BINT dp[45][45], D[45][45];
int main() {
cin >> n >> m >> s;
s = " " + s;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
D[i][j] = s.substr(i, j - i + 1);
// cout << D[i][j] << " ";
}
for (int i = 1; i <= n; i++)
dp[i][0] = D[1][i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (j >= i) break;
for (int k = j; k < i; k++)
if (dp[i][j] < dp[k][j - 1] * D[k + 1][i])
dp[i][j] = dp[k][j - 1] * D[k + 1][i];
}
cout << dp[n][m];
return 0;
}
```