这个最大最小应该怎么写

Question

3.6 最大最小

★实验任务
TonyY 最近喜欢上了数学，今天他研究一个只有加号和乘号，运算数为整数，大小在 1-9 之间的表达式，你可以任意地往里加括号，如何让表达式的值最大或者最小？

★数据输入

输入仅一行，为上述的算式，长度 n（1<=n<=200）,保证算式合法。

★数据输出

输出添括号后的算式最大值和最小值，由于答案较大，请将答案对870764322 求余后输出。

输入示例

1+2*3

输出示例

9

7

Answer 1

【以下回答由 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求余。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7666412
• 你也可以参考下这篇文章：有一个整数数列，其前三项分别为1、2、3，从第四项开始，每项均为其相邻的前三项之和的1/2。问，该数列从第几项开始，其数值超过某个整数n
• 除此之外, 这篇博客: 详解：本题要求实现一个函数，判断任一给定整数N是否满足条件：它是完全平方数，又至少有两位数字相同，如144、676等。中的 5.代码如下： 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^