一个原创题（3）

文章目录

• 一个原创题的思考
• 四则运算符最大连续子数组
• • 题目链接：
  • 题目描述
  • 计算规则如下：
  • 输入格式
  • 输出格式
  • 输入样例
  • 输出样例
  • 输入样例
  • 输出样例
  • 说明：
  • 参考代码：
  • 备选样例：
  • 样例一
  • 输入样例
  • 输出样例
  • 样例二
  • 输入样例
  • 输出样例
  • 样例三
  • 输入样例
  • 输出样例
  • 样例四
  • 输入样例
  • 输出样例
  • 样例五
  • 输入样例
  • 输出样例
  • 样例六
  • 输入样例
  • 输出样例
  • 样例七
  • 输入样例
  • 输出样例
  • 样例九
  • 输入样例
  • 输出样例
  • 样例十
  • 输入样例
  • 输出样例
  • 注：

一个原创题的思考

四则运算符最大连续子数组

题目链接：

https://www.luogu.com.cn/problem/U693809 此题以被我录进洛谷中，欢迎来战，也希望大佬们多提提意见!!!

题目描述

给定一个全部元素均不为 0 的浮点（double）数组。你可以任选数组中一段非空的连续子数组，在选出的子数组中，每两个相邻数字之间，自由选择填入 +、-、*、/ 四种运算符中的一个。

计算规则如下：

请你求出所有可选方案里，表达式能够算出的最大数值。

输入格式

第一行输入一个整数 n(n<250)，代表数组的元素总个数。

第二行输入n个浮点数，为数组的全部元素。

输出格式

输出一个浮点数值，表示能够算出的最大结果，结果精确到小数点后一位。

输入样例

2

1.5 2.0

输出样例

3.5

输入样例

3

1.0 0.001 0.001

输出样例

1000000.0

说明：

最大值为1.0/0.001/0.001=1000000.0

参考代码：

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
const int MAXN = 500;
const double INF = 1e18;
const double EPS = 1e-12;
double a[MAXN];
double dp_max[MAXN][MAXN], dp_min[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
double ans = –INF;
for(int i=1;i<=n;i++){
dp_max[i][i] = a[i];
dp_min[i][i] = a[i];
ans = max(ans, dp_max[i][i]);
}
for(int len=2;len<=n;len++){
for(int l=1;l+len–1<=n;l++){
int r = l + len – 1;
dp_max[l][r] = –INF;
dp_min[l][r] = INF;
for(int k=l;k<r;k++){
double t1 = dp_max[l][k] + dp_max[k+1][r];
double t2 = dp_max[l][k] + dp_min[k+1][r];
double t3 = dp_min[l][k] + dp_max[k+1][r];
double t4 = dp_min[l][k] + dp_min[k+1][r];
double t5 = dp_max[l][k] – dp_max[k+1][r];
double t6 = dp_max[l][k] – dp_min[k+1][r];
double t7 = dp_min[l][k] – dp_max[k+1][r];
double t8 = dp_min[l][k] – dp_min[k+1][r];
double now_max = max({t1,t2,t3,t4,t5,t6,t7,t8});
double now_min = min({t1,t2,t3,t4,t5,t6,t7,t8});
dp_max[l][r] = max(dp_max[l][r], now_max);
dp_min[l][r] = min(dp_min[l][r], now_min);
}
double mul_max = a[l];
double mul_min = a[l];
for(int p=l+1;p<=r;p++){
double n1 = mul_max * a[p];
double n2 = mul_min * a[p];
double n3 = mul_max / a[p];
double n4 = mul_min / a[p];
double nmx = max({n1,n2,n3,n4});
double nmn = min({n1,n2,n3,n4});
mul_max = nmx;
mul_min = nmn;
}
dp_max[l][r] = max(dp_max[l][r], mul_max);
dp_min[l][r] = min(dp_min[l][r], mul_min);
ans = max(ans, dp_max[l][r]);
}
}
cout << fixed << setprecision(1) << ans << endl;
return 0;
}

备选样例：

样例一

输入样例

4

0.1 0.2 0.3 0.4

输出样例

4.2

样例二

输入样例

5

-0.5 2.0 -3.0 4.0 -5.0

输出样例

120.0

样例三

输入样例

4

10.0 0.2 -0.5 99.0

输出样例

149.5

样例四

输入样例

4

8.0 0.5 0.2 10.0

输出样例

800.0

样例五

输入样例

4

20.0 0.1 100.0 0.1

输出样例

200000.0

样例六

输入样例

3

-2.0 -3.0 0.5

输出样例

12.0

样例七

输入样例

5

0.01 0.1 0.1 10.0 1.0

输出样例

12.0

样例九

输入样例

4 -10.0 -0.1 0.2 -1.0

输出样例

501.0

样例十

输入样例

3

1.0 -2.0 3.0

输出样例

7.0

其实我在思考这个题目的时候是在前一篇博客的商最大子数组问题，那个和力扣的第152题的乘法最大子数组其实是一样的，在同时维护一个最大值和最小值的动态规划，但其实这个题的灵感来自于我学习栈和对子数组问题的研究，我思考能不能把他们融合在一起，所以本学生就想到了这个题，这个题的难度在于中缀表达式和子数组问题的特点它都兼具，在考虑运算的时候要看先乘除后加减的优先级，还要看看在啥时候能取到最大值，不过我把这个题改为浮点数组的目的是： 第一，如果我们是一个整数数组，那么我其实除法，加法，减法没有那么多地需要考虑，为啥？因为我如果是整数，在全正的情况下就从头乘到尾，如果有负数，才要考虑加减，特别地还有特判一下1和-1的情况，因为加1和减-1比乘除来的大，但总的来说最优解是乘法的居多。 第二，改为浮点数组是有好处的，就是说我的样例三： 4 10.0 0.2 -0.5 99.0 这组样例不是只靠乘除就能解决问题的，是要更多引入加减运算，那149.5就是这样算出来的： 10.0/0.2–0.5+99.0=149.5(在我认为减一个负数表达为–0.5是没有歧义），那有没有更优解呢？应该来说是没有的，因为10.0遇到0.2要想最大就只能去除，再看后面的-0.5和99.0，我在这个数组中只有一个负数，所以说不能去乘除一个负数，那我是–0.5*99.0吗，也不行，这样大数会被拉小，不可能达到最大。 第三，其实无论是整数数组还是浮点数组，他的解法都是动态规划DP,只是说如果改为了浮点数组那他就难度更大，此外这个题其实可以用回溯折枝DFS来解的。

注：

这道题也算是我学习的一个总结，其实这个题我承认他是存在漏洞的，在想样例的时候没有更多数和更多情况的考虑，代码的写作也用AI改了一下，这道题总的来说是综合性的且难度不小的，所以在此提出我的灵感和想法，也希望大佬们能多发现我的错误，多提出这道题的问题，十分感谢！！！