「线性DP」乘积最大
本题为3月20日23上半学期集训每日一题中A题的题解
题面
题目描述
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串:312, 当N=3,K=1时会有以下两种分法:
- \(3 \times 12 = 36\)
- \(31 \times 2 = 62\)
这时,符合题目要求的结果是:\(31 \times 2 = 62\) 。
现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。
输入
第一行共有2个自然数N,K( \(4\leq N\leq 40,1\leq K\leq 6\) )
第二行是一个长度为N的数字串。
输出
输出所求得的最大乘积(一个自然数)。
样例输入
4 2
1231
样例输出
62
思路分析
这题看完题目之后我的第一反应是直接二进制枚举
或者DFS
,然后看了眼数据量,时间应该是不够的(实际上这题给的数据量是假的,真正的数据量很小,直接这么写应该也能过).不过可以发现此题是具有最优子结构的性质的,所以显然可以把DFS
改成动态规划
来进行求解.
那如何进行状态转移呢?我们先从DFS
的角度来想.如果此题我们采用DFS
的思路解题,我们的思路应该是类似下面这样的:
- 遍历所有能放乘号的间隔,以这个间隔把整个数列成两半
- 对左边那一半(你愿意也可以对右边那一半,但是这样改成
动态规划
后循环要倒着来,不推荐坑自己)递归调用此函数,即递归地求出左边插入剩下数量的乘号后的最大值(为了保证左半段能放下剩下的乘号,左半段的间隔数必须大于等于剩下的乘号数) - 将递归算出的左半边乘上右半边,即是当前划分方案的值(为了保证右半边有数,所以左半边的长度最大只能是当前长度减一)
- 取所有划分方案的最大值
下面是上述思路的简单伪实现:
// i为需要插入的乘号数量,j为当前最后一个元素的下标(这个参数此处可以省略,但是不推荐,因为动态规划里要用到),num为当前的数,数据类型仅为代号
int count(int i, int j, string num) {
int res = 0;
for (int k = i - 1; k < j; k++) { // 切分后左半段最后一个元素下标,从剩下乘号数遍历到倒数第二个数
res = max(res, count(i - 1, k, /*num[0:k](指num从0到i连起来的字符串(切片),为了方便阅读,这里包括边界)*/) * /*int(num[k + 1:j])*/);
}
return res;
}
DFS
改成动态规划
只需要用一个数组来代替递归即可:
- 首先,数组的下标对应函数的参数,数组中存放函数在不同参数情况下的返回值;
- 接着,我们把递下去的过程去掉,只保留传回来的过程(即递归改循环);
- 最后我们需要的状态转移方程,就是把递归调用改成取数组中的元素即可.
所以此题可得如下状态转移方程(为方便阅读,切片包含头尾):
\(dp[i][j] = \begin{cases} 0, j \leq i - 1 (代码里偷懒没体现这一点,因为初始值我全部赋了0)\\ num[0:j], i==0\\ max_{i - 1 \leq k < j}(dp[i - 1][k] * num[k + 1:j]), 0 < i < n \end{cases}\)
(上述这种从DFS
角度思考动态规划
的方法,被y总(NOI金牌选手,报送北大,ACWing创始人)总结为闫氏dp分析法
,他本人认为这种分析方法本质上是从集合角度出发的思考.这种思考方法非常有效,可以在遇到一些较难分析状态转移的时候尝试)
dp问题就是状态的表示和计算,表示就是集合+属性,计算就是集合的划分,要不重不漏,怎么划分呢,寻找最后一个不同点.---闫学灿
所以这题的代码只要把上述的状态转移方程实现成一个程序即可,最后一个状态即为答案.
题目里说 \(n \leq 40\) ,这个数据大小是超过C++最大的数据类型的(int128),所以必须使用高精度算法
.但实际上测试下来,直接用int类型也能存,这个n实际上可能封顶是9(诈骗行为,建议连夜下载国家反诈中心app),所以单单就AC来说,不需要用到高精度算法
,直接算就行.由于我个人做高精度题目都是用Python的(Python会被卡的题目就交给队友),所以这里给出的C++代码仅为AC代码,实际上需要将数值的乘改为高精度乘法.
参考代码
C++版本(仅AC)
时间复杂度: \(O(N^3K)\) (计入字符串切片使用时间,可以通过先计算出所有切片来优化一个N)
空间复杂度: \(O(NK)\)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
string num;
cin >> num;
vector<vector<int>> dp(m + 1, vector<int>(n, 0)); // 第一维为乘号数,第二维为当前末下标
// 维护初始状态
dp[0][0] = num[0] - '0';
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] * 10 + num[i] - '0'; // 这里能直接推就不建议用substr,当前你也可以再维护一个二维数组,求出所有substr.
}
// 状态转移
for (int i = 1; i <= m; i++) { // 乘号数
for (int j = 0; j < n; j++) { // 当前末下标
for (int k = i - 1; k < j; k++) { // 乘号放置位置(切分后左半段最后一个元素下标)
dp[i][j] = max(dp[i][j],
dp[i - 1][k] * stoi(num.substr(k + 1, j - k)));
}
}
}
cout << dp[m][n - 1] << "\n";
return 0;
}
python版本
如果此题的n能到达40,那么在C++中是存放不了的,需要使用高精度算法
.而对时间要求不高的地方,可以用python来编写需要用到高精度算法
的代码.py原生支持无限大的整型(真·无限大,想存多大存多大),同时也原生具有无损浮点数类型的支持,所以很适合在对时间要求不高的地方拿来代替高精度算法,而且写起来很快,同时也不容易出现错在高精度上(抄错板子)导致查错查半天的情况.
时间复杂度: \(O(N^3K)\) (计入字符串切片使用时间,可以通过先计算出所有切片来优化一个N)
空间复杂度: \(O(NK)\)
#!/usr/bin/env python3
# coding=utf-8
n,m = map(int,input().split()) # 输入n,m
s = input() # 输入数字字符串
dp = [[0] * n for i in range(0,m + 1)] # dp用二维数组,注意二维不能用乘,必须用行for来生成
dp[0] = [int(s[:i]) for i in range(1,n + 1)] # 初始化初始状态
for i in range(1,m + 1): # 乘号数量
for j in range(0,n): # 终点下标
for k in range(i - 1,j): # 乘号位置
dp[i][j] = max(dp[i][j], dp[i - 1][k] * int(s[k + 1:j + 1])) # 状态转移
print(dp[m][n-1]) # 输出
"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德
这里是浙江理工大学22届ACM集训队的成员一枚鸭!
本文首发于博客园,作者:星双子,除了我自己的转载请注明原文链接:https://www.cnblogs.com/geministar/p/zstu23_3_20_A.html
热门相关:仙城纪 寂静王冠 网游之逆天飞扬 天启预报 豪门闪婚:帝少的神秘冷妻