Scammy Game Ad - 题解

比赛与标签

比赛: Codeforces Round 1008 (Div. 2) 标签: dp, greedy, implementation 难度: *1800

喵喵，这题说什么呀？

你好呀，指挥官！今天我们来玩一个超级有趣的游戏，喵~

游戏是这样的：我们一开始有两条路，左边和右边，每条路上都有1个小人。我们要带着这些小人通过 n 对门。每一对门都由一个左门和一个右门组成，的说。

每个门都有一个神奇的效果：

• 加法门 (+ a): 直接变出 a 个新的小人。
• 乘法门 (x a): 如果这条路上当前有 c 个小人，它就会变出 (a-1) * c 个新的小人。

重点来啦！在每一对门这里，左门和右门变出的所有新小人，会全部汇集到一个“新人池”里。然后，我们可以把这些“新人池”里的小人 任意地 分配到左边或者右边的路上去！但是，原来路上的小人是不能换路的哦~

我们的目标是，在通过所有 n 对门之后，让两条路上的小人总数（左路 + 右路）达到最大！你能帮帮本喵吗？(ฅ'ω'ฅ)

来和喵娘一起想办法吧！

看到这道题，第一反应可能是：“哇，每一步都有好多分配方案，这得有多少种可能性呀！” 如果新人池里有 G 个小人，我们就有 G+1 种分配方法。如果每一步都去枚举，状态数量会像猫毛一样疯长，肯定会超时的说！

所以，我们需要更聪明的办法，喵~ 让我们来分析一下问题的本质。

关键的简化：帕累托前沿

我们把每一条路的人数看作一个坐标 (l, r)，代表左路有 l 个人，右路有 r 个人。我们的目标就是最大化 l + r。

在任何一步之后，我们可能会得到很多很多个可能的 (l, r) 状态。但是，有些状态明显比其他状态要好。比如说，状态 (10, 8) 就比状态 (9, 7) 要好，因为它的 l 和 r 都更大。我们称 (10, 8) 支配 (9, 7)。

一个聪明的策略是，我们只需要记录那些不被任何其他状态支配的“最优”状态集合。这些状态在二维平面上，会形成一条“上-右”方向的边界线，在学术上这叫做帕累托前沿 (Pareto Front)，是不是听起来很酷，呐？

究极简化：只关心端点！

即使只记录帕累托前沿，上面的状态点也可能有很多。但是！这道题有一个绝妙的性质，让我们可以进行究极简化！

我们可以证明，在每一步之后，这个帕累托前沿都是一个凸包的上边界。而对于一个凸形，我们其实只需要关心它的端点就足够了！

这是为什么呢？喵~ 让我们来想一下：

1. 新的端点从哪里来？ 假设在第 i-1 步之后，我们知道了帕累托前沿的两个端点：

   • state_L: 左路人数 l 达到最大的状态。
   • state_R: 右路人数 r 达到最大的状态。

   当我们通过第 i 对门时，要产生新的帕累托前沿。新前沿的“最左上角”（也就是新的 state_L，l 最大）和“最右下角”（也就是新的 state_R，r 最大）会从哪里来呢？

2. 线性规划的直觉 新产生的 l 值，是旧的 l、r 和新产生的人数的线性组合。在一个凸集（我们的帕累托前沿）上求一个线性函数的最值，最值一定是在凸集的顶点（也就是端点）上取到的！

   所以，第 i 步的 state_L 一定是由第 i-1 步的 state_L 或 state_R 演变而来的！同理，第 i 步的 state_R 也是如此。

最终的贪心+DP策略

这下问题就变得超级简单了！我们根本不需要记录整个帕累托前沿，只需要在每一步维护两个状态：

• state_L: 当前所有可达状态中，l 值最大的那个状态。
• state_R: 当前所有可达状态中，r 值最大的那个状态。

算法流程如下，喵~

1. 初始化: 第0步，我们只有一个状态 (1, 1)。所以 state_L = {1, 1} 且 state_R = {1, 1}。

2. 迭代: 对每一对门 i = 0 to n-1： a. 拿出上一轮的 state_L 和 state_R。 b. 计算如果当前状态是 state_L，通过这对门能产生多少新小人 g_L。 c. 计算如果当前状态是 state_R，通过这对门能产生多少新小人 g_R。 d. 现在我们有四个“候选”的下一轮端点： * 从 state_L 演变而来：把 g_L 全给左边得到 cand_A；全给右边得到 cand_B。 * 从 state_R 演变而来：把 g_R 全给左边得到 cand_C；全给右边得到 cand_D。 e. 更新下一轮的 state_L: 在 cand_A 和 cand_C 中，选一个 l 值更大的。如果 l 值一样大，就选 r 值更大的那个（因为它更优，更能支配别的状态）。 f. 更新下一轮的 state_R: 在 cand_B 和 cand_D 中，选一个 r 值更大的。如果 r 值一样大，就选 l 值更大的那个。

3. 结果: 走完所有门之后，我们得到了最终的 state_L 和 state_R。这两个状态都是帕累托最优的，所以最终答案就是 max(state_L.l + state_L.r, state_R.l + state_R.r)。

这个方法巧妙地把一个复杂的DP问题，转化成了一个每步只维护两个状态的简单迭代过程，是不是很神奇呀！

看喵娘的代码魔法！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>

// 为了方便，我们使用标准命名空间的说
using namespace std;

// 人数可能会很大，用 long long 才不会溢出哦，喵~
using ll = long long;

// 用一个结构体来表示状态 (左路人数, 右路人数)，很清晰呐
struct State {
    ll l, r;
};

// 这个函数用来计算在当前状态下，通过一对门能产生多少新小人
ll get_total_new(char op_l, ll val_l, char op_r, ll val_r, ll current_l, ll current_r) {
    ll gen_l;
    if (op_l == '+') {
        gen_l = val_l; // 加法门，直接增加 val_l
    } else { // op_l == 'x'
        gen_l = (val_l - 1) * current_l; // 乘法门，增加 (val_l - 1) 倍
    }

    ll gen_r;
    if (op_r == '+') {
        gen_r = val_r; // 同理
    } else { // op_r == 'x'
        gen_r = (val_r - 1) * current_r;
    }

    return gen_l + gen_r; // 返回新小人的总数
}

// 每个测试用例的主逻辑都在这里喵
void solve() {
    int n;
    cin >> n;

    // 用一个 vector 来存储 n 对门的信息
    vector<tuple<char, ll, char, ll>> gates(n);
    for (int i = 0; i < n; ++i) {
        char op_l, op_r;
        ll val_l, val_r;
        cin >> op_l >> val_l >> op_r >> val_r;
        gates[i] = make_tuple(op_l, val_l, op_r, val_r);
    }

    // 我们只追踪帕累托前沿的两个端点状态
    // state_L: l 值最大的状态
    // state_R: r 值最大的状态
    // 初始时，只有一个状态 (1, 1)，所以两个端点是同一个
    State state_L = {1, 1};
    State state_R = {1, 1};

    for (int i = 0; i < n; ++i) {
        auto [op_l, val_l, op_r, val_r] = gates[i];

        // 分别计算从当前两个端点状态出发，能产生多少新小人
        ll g_L = get_total_new(op_l, val_l, op_r, val_r, state_L.l, state_L.r);
        ll g_R = get_total_new(op_l, val_l, op_r, val_r, state_R.l, state_R.r);

        // 从当前的两个端点，可以产生四个“极端”的候选新端点
        // 把所有新小人全部分配到一边
        // 从 state_L 产生
        State cand_A = {state_L.l + g_L, state_L.r}; // 全给左边
        State cand_B = {state_L.l, state_L.r + g_L}; // 全给右边
        // 从 state_R 产生
        State cand_C = {state_R.l + g_R, state_R.r}; // 全给左边
        State cand_D = {state_R.l, state_R.r + g_R}; // 全给右边

        State next_state_L, next_state_R;

        // 决定新的 l-最大化 端点 (next_state_L)
        // 它只能从把新人全给左边的 cand_A 或 cand_C 中产生
        if (cand_A.l > cand_C.l) {
            next_state_L = cand_A;
        } else if (cand_C.l > cand_A.l) {
            next_state_L = cand_C;
        } else {
            // 如果 l 值相同，选择 r 值更大的那个，因为它更优
            next_state_L = (cand_A.r > cand_C.r) ? cand_A : cand_C;
        }

        // 决定新的 r-最大化 端点 (next_state_R)
        // 它只能从把新人全给右边的 cand_B 或 cand_D 中产生
        if (cand_B.r > cand_D.r) {
            next_state_R = cand_B;
        } else if (cand_D.r > cand_B.r) {
            next_state_R = cand_D;
        } else {
            // 如果 r 值相同，选择 l 值更大的那个
            next_state_R = (cand_B.l > cand_D.l) ? cand_B : cand_D;
        }
        
        // 更新端点状态，准备进入下一轮循环
        state_L = next_state_L;
        state_R = next_state_R;
    }

    // 最终答案是两个最终端点状态的总和中的较大者
    cout << max(state_L.l + state_L.r, state_R.l + state_R.r) << "\n";
}

int main() {
    // 加速一下输入输出，跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

跑得快不快呀？

• 时间复杂度: O(n) 的说。对于每个测试用例，我们只对 n 对门进行一次遍历。在循环内部，所有的计算和比较都是常数时间操作。所以总的时间复杂度和门的数量成正比，非常快！
• 空间复杂度: O(n) 的说。我们主要需要空间来存储 n 对门的信息。算法本身在迭代过程中只需要常数个变量来存储两个端点状态，所以空间开销主要是输入数据本身。

这次学到了什么喵？

这道题真是太有启发性了！它告诉我们，当遇到状态空间可能爆炸的DP问题时，不要害怕，要静下心来寻找问题的特殊性质，喵~

1. DP状态优化: 核心思想是动态规划，但我们通过观察，极大地优化了需要维护的状态。
2. 贪心与帕累托前沿: 解法的关键是发现我们只需要追踪帕累托前沿的端点。这是一个非常强大的技巧，适用于一些二维平面上的优化问题。它把一个看似复杂的问题，变成了一个简单的贪心选择过程。
3. 凸性思想: 这种端点思想的背后，其实是凸集和线性规划的影子。虽然我们不需要严格证明，但有这种直觉可以帮助我们找到正确的简化方向。

总之，以后再遇到类似的问题，记得想一想：是不是可以只维护几个“最极端”的“最优”状态呢？说不定就能找到突破口啦！加油哦，指挥官！(>ω<)ﾉ