3.6 最大最小
★实验任务
TonyY 最近喜欢上了数学，今天他研究一个只有加号和乘号，运算数为整数，大小在 1-9 之间的表达式，你可以任意地往里加括号，如何让表达式的值最大或者最小？
★数据输入
输入仅一行，为上述的算式，长度 n（1<=n<=200）,保证算式合法。
★数据输出
输出添括号后的算式最大值和最小值，由于答案较大，请将答案对870764322 求余后输出。
输入示例
1+2*3
输出示例
9
7
【以下回答由 GPT 生成】
#include <stdio.h>
// 计算加法
int add(int a, int b) {
return (a + b) % 870764322;
}
// 计算乘法
int multiply(int a, int b) {
return (a * b) % 870764322;
}
// 计算算式的最大值和最小值
void calculate(char *expression) {
int n = strlen(expression);
int nums[n/2 + 1]; // 数字数组
char ops[n/2]; // 运算符数组
int num_count = 0; // 数字的数量
int ops_count = 0; // 运算符的数量
// 解析算式
for (int i = 0; i < n; i++) {
if (expression[i] >= '0' && expression[i] <= '9') {
nums[num_count++] = expression[i] - '0';
} else {
ops[ops_count++] = expression[i];
}
}
// 初始化最大值和最小值的矩阵
int dp[n/2 + 1][n/2 + 1];
for (int i = 0; i <= n/2; i++) {
for (int j = 0; j <= n/2; j++) {
dp[i][j] = 0;
}
}
// 求解最大值和最小值
for (int len = 2; len <= n/2 + 1; len++) {
for (int i = 0; i <= n/2 - len + 1; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
int a = dp[i][k];
int b = dp[k+1][j];
if (ops[k] == '+') {
dp[i][j] = max(dp[i][j], add(a, b));
} else {
dp[i][j] = max(dp[i][j], multiply(a, b));
}
}
}
}
// 输出最大值和最小值
printf("%d\n", dp[0][n/2]);
printf("%d\n", dp[0][n/2]);
}
int main()
{
char expression[201];
scanf("%s", expression);
calculate(expression);
return 0;
}
由于运行时间和内存限制的原因，我们不能通过将所有可能的括号方案都尝试一遍来求解最大值和最小值。我们可以使用动态规划来解决这个问题。定义一个二维数组dp[i][j]，表示从第i个数字到第j个数字之间的算式最大值（或最小值）。状态转移方程为：
dp[i][j] = max/min{dp[i][k] + dp[k+1][j]}，其中i <= k < j，运算符为加号或乘号。
根据这个状态转移方程，我们可以使用动态规划的方法依次计算出所有可能的dp[i][j]的值。最终的结果即为dp[0][n/2]（其中n为算式的长度）。
由于答案可能较大，对最大值和最小值都要对870764322求余。
【相关推荐】
引用 皆我百晓生 小程序回复内容作答：
这个问题可以通过使用动态规划来解决，我们可以定义两个数组来保存当前位置的最大和最小值。
具体的算法如下：
下面是一个示例的 C 语言代码实现：
#include <stdio.h>
#define MOD 870764322
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
char expression[201];
int maxVal[201], minVal[201];
int n;
scanf("%s", expression);
n = strlen(expression);
maxVal[0] = expression[0] - '0'; // 初始化第一个数字
minVal[0] = expression[0] - '0';
for (int i = 2; i < n; i += 2) {
int currentVal = expression[i] - '0';
if (expression[i-1] == '+') {
maxVal[i] = max(maxVal[i-2] + currentVal, maxVal[i]);
minVal[i] = min(minVal[i-2] + currentVal, minVal[i]);
} else if (expression[i-1] == '*') {
maxVal[i] = max(maxVal[i-2] * currentVal, maxVal[i]);
minVal[i] = min(minVal[i-2] * currentVal, minVal[i]);
}
}
printf("%d\n", maxVal[n-1] % MOD);
printf("%d\n", minVal[n-1] % MOD);
return 0;
}
在上述示例中，我们通过动态规划的方法计算了表达式的最大值和最小值，并且最终对结果取余后输出。请注意，代码中未包含完整的输入处理部分和错误检查部分，您可以根据需要进行调整和扩展。