题解：P16404 [ECUSTPC 2026 Spring] 海底捞月

a1b2c3_ · 2026-05-13 13:41:17 · 题解

题目分析

有一个正整数 x，以及四种操作：

求经过操作后，最终 x 的最大值。

解题思路

先找出每一种操作的先后顺序。

能够证明的是证明，操作 3 一定在最后使用。

对于操作 1 和 3：

若先进行操作 1，再进行操作 3，则 t_1 = \left\lfloor \frac{6 \left\lfloor 10\sqrt{x} \right\rfloor}{5} \right\rfloor。
\frac{6 \left\lfloor 10\sqrt{x} \right\rfloor}{5} - 1 < t_1\\ \frac{6(10\sqrt{x} - 1)}{5} - 1 < t_1\\ 12\sqrt{x} - \frac{11}{5} < t_1
若先进行操作 3，再进行操作 1，则 t_2 = \left\lfloor 10\sqrt{\left\lfloor\frac{6x}{5}\right\rfloor}\right\rfloor。
t_2 \le 10\sqrt{\left\lfloor\frac{6x}{5}\right\rfloor}\\ t_2 \le 10\sqrt{\frac{6x}{5}}\\ t_2 \le \sqrt{120x} < 11\sqrt{x}
而当 x > 4 时：\frac{11}{5} < \sqrt{x}，所以 t_2 < 11\sqrt{x} < 12\sqrt{x} - \frac{11}{5} < t_1，即 t_2 < t_1。

实际上，打表就可以看出 \forall x \in \{1,2,3,4\},\ t_2 < t_1。 x t_1 t_2

1 12 10

2 16 14

3 20 17

4 24 20
对于操作 2 和 3：

若先进行操作 2，再进行操作 3，则 t_3 = \left\lfloor \frac{6 (\left\lfloor\frac{7x}{10}\right\rfloor+30)}{5} \right\rfloor。
\frac{6 \left\lfloor\frac{7x}{10}\right\rfloor+180}{5} - 1 < t_3\\ \frac{6(\frac{7x}{10}-1)+175}{5} < t_3\\ \frac{\frac{21x}{5}+169}{5} < t_3\\ \frac{21x}{25}+\frac{169}{5} < t_3
若先进行操作 3，再进行操作 2，则 t_4 = \left\lfloor\frac{7\left\lfloor \frac{6x}{5} \right\rfloor}{10}\right\rfloor+30。
t_4 \le \frac{7\left\lfloor \frac{6x}{5} \right\rfloor}{10}+30\\ t_4 \le \frac{7\times \frac{6x}{5}}{10}+30\\ t_4 \le \frac{21x}{25}+30
因为 \frac{169}{5} = 33.8 > 30，所以 t_4 \le \frac{21x}{25}+30 < \frac{21x}{25}+\frac{169}{5} < t_3，即 t_4 < t_3。
对于操作 4 和 3：

若先进行操作 4，再进行操作 3，则 t_5 = \left\lfloor \frac{6(x + 5)}{5} \right\rfloor。
\frac{6(x + 5)}{5} - 1 < t_5\\ \frac{6x}{5} + 5 < t_5
若先进行操作 3，再进行操作 4，则 t_6 = \left\lfloor \frac{6x}{5} \right\rfloor + 5。
t_6 \le \left\lfloor \frac{6x}{5} \right\rfloor + 5\\ t_6 \le \frac{6x}{5} + 5\\
所以 t_6 \le \frac{6x}{5} + 5 < t_5，即 t_6 < t_5。

实际上，打表就可以看出 \forall x \in \{1,2,3,4\},\ t_2 < t_1。	x	t_1	t_2
1	12	10
2	16	14
3	20	17
4	24	20

综上，操作 3 一定在最后使用。

并且可以知道的是，当 x \ge 100 时，操作 1, 2 均没有正收益。

另外，我们可以手算出对于任意的正整数，至多进行 9 次操作 1 或 11 次操作 2 便会没有正收益。

最后，当 x < 100 时，操作 4 至多执行 20 次，否则 x 一定大于 100。

分为两个阶段讨论：

直接 DP 预处理即可。
先执行操作 $4$，再执行操作 $3$。

时间复杂度分析

DP 时间复杂度为 O(\min(a_1, 9)\cdot\min(a_2, 11)\cdot\min(a_4, 20))。

操作 3, 4 最多执行 a_3 + a_4 次。

所以时间复杂度为 O(\min(a_1, 9)\cdot\min(a_2, 11)\cdot\min(a_4, 20) + T(a_3 + a_4))。

由于 \min(a_1,9),\min(a_2,11),\min(a_4,20) 均为有界常数，所以时间复杂度可以看成 \Theta(T(a_3 + a_4))。

代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

// res[x][i][j][k] : x进行i次操作1、j次操作2后的数值、k次操作4后的数值
int res[101][21][10][12];

void getValue(int (&dp)[21][10][12])
{
    // 先预处理 0次操作1，依次做j次操作2
    for (int j = 0; j < 11; j++)
    {
        dp[0][0][j + 1] = dp[0][0][j] * 7 / 10 + 30;
    }

    // 递推填dp表：i次操作1，j次操作2
    for (int i = 0; i < 9; i++)
    {
        // 第i+1行第0列：只做操作1
        dp[0][i + 1][0] = (int)sqrt(dp[0][i][0] * 100.0);
        for (int j = 0; j < 11; j++)
        {
            // 选：先操作2 或 先操作1 取最大
            int op2_val = dp[0][i + 1][j] * 7 / 10 + 30;
            int op1_val = (int)sqrt(dp[0][i][j + 1] * 100.0);
            dp[0][i + 1][j + 1] = max(op2_val, op1_val);
        }
    }

    // 枚举逐步加5（操作4）
    for (int t = 0; t < 20; t++)
    {
        int (&dp2)[10][12] = dp[t + 1];

        // 更新一格
        dp2[0][0] = dp[t][0][0] + 5;

        // 更新一行（0次操作1）
        for (int j = 0; j < 11; j++)
        {
            int next2 = dp2[0][j] * 7 / 10 + 30;
            dp2[0][j + 1] = max(next2, dp[t][0][j + 1] + 5);
        }

        // 更新dp表
        for (int i = 0; i < 9; i++)
        {
            int newRow0 = max((int)sqrt(dp2[i][0] * 100.0), dp[t][i + 1][0] + 5);
            dp2[i + 1][0] = newRow0;

            for (int j = 0; j < 11; j++)
            {
                int v2 = dp2[i + 1][j] * 7 / 10 + 30;
                int v1 = (int)sqrt(dp2[i][j + 1] * 100.0);
                int v4 = dp[t][i + 1][j + 1] + 5;
                dp2[i + 1][j + 1] = max({v2, v1, v4});
            }
        }
    }
}

// 输出__int128大数
void print(__int128 num)
{
    if (num == 0)
    {
        cout << 0;
        return;
    }
    string res;
    while (num > 0)
    {
        res += (char)('0' + num % 10);
        num /= 10;
    }
    reverse(res.begin(), res.end());
    cout << res;
}

int main()
{
    for (int i = 1; i < 101; ++i) {
        res[i][0][0][0] = i;
        getValue(res[i]);
    }

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        int x, a, b, c, d;
        cin >> x >> a >> b >> c >> d;

        // 限制范围
        a = min(a, 9);
        b = min(b, 11);

        int best = x + d * 5;
        if (x < 100)
        {
            best = res[x][min(d, 20)][a][b] + max(0, d - 20) * 5;
        }

        // 执行c次操作3：向下取整 1.2倍
        __int128 ans = best;
        for (int i = 0; i < c; i++)
        {
            ans = ans * 6 / 5;
        }

        print(ans);
        cout << '\n';
    }
    return 0;
}