题解：P16440 [XJTUPC 2026] 公式战士

· · 题解

洛谷 P16440 题解

给定初始值 x 和 n 个步骤。每步有两个四则运算表达式，需选择其一代入上一步结果计算。求 n 步后的最大值。

其实这题的核心在于发掘四则运算的性质。我们每次面对加、减、乘、除，这些运算在整数域上其实都有一个很明显的特点：具有单调性。

这意味着什么呢？如果上一步我们能得到的所有结果构成了一个集合，那么将这个集合里的所有数进行同一种四则运算，产生的新集合的极值（最大值和最小值），一定是由原集合的极值推导出来的。换句话说，中间那些不大不小的结果，无论怎么运算，也无法在下一步“逆袭”成为新的最大值或最小值。

顺着这个思路，做法就很自然了。我们根本不需要关心每一步能算出多少种不同的结果，只需要贪心地盯住两个端点：当前能达到的最大值和最小值。

设 dp_{\max, i} 和 dp_{\min, i} 分别为前 i 步能得到的最大值和最小值。 对于第 i 步的两个表达式，我们把上一步的 dp_{\max, i - 1} 和 dp_{\min, i - 1} 分别代进去算。这样一共会产生 4 个结果。在这 4 个结果中，挑出最大的作为 dp_{\max, i}，挑出最小的作为 dp_{\min, i}，然后继续往下推即可。

时间复杂度 O(n)，空间复杂度 O(n)（可滚动数组优化至 O(1)）。

代码实现如下，注意减法和除法运算时 x 的位置对结果的影响：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int calc(int x, string a, string op, string b) { 
    int num = a == "x" ? stoll(b) : stoll(a);
    if (op == "+") {
        return x + num;
    } else if (op == "-") {
        return (a == "x" ? x - num : num - x); // 注意减数与被减数的位置
    } else if (op == "*") {
        return x * num;
    } else if (op == "/") {
        return (a == "x" ? x / num : num / x); // 注意除数与被除数的位置
    }
}

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> dpmax(n + 1, 0), dpmin(n + 1, 0);
    dpmax[0] = dpmin[0] = x; 
    for (int i = 1; i <= n; i++) {
        string a, b, c, d, e, f;
        cin >> a >> b >> c >> d >> e >> f;
        // 把上一步的极值代入两个表达式，产生 4 个结果，分别取最大和最小
        dpmax[i] = max({calc(dpmax[i - 1], a, b, c), calc(dpmax[i - 1], d, e, f), calc(dpmin[i - 1], a, b, c), calc(dpmin[i - 1], d, e, f)}); 
        dpmin[i] = min({calc(dpmax[i - 1], a, b, c), calc(dpmax[i - 1], d, e, f), calc(dpmin[i - 1], a, b, c), calc(dpmin[i - 1], d, e, f)}); 
    }
    cout << dpmax[n] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cout.tie(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

求过