https://codeforces.com/problemset/problem/2078/D

一、题意

有 n 对门，每对门都有左、右两个通道。初始时，左右通道各有一个人，并且这些人不能中途切换通道。

当我们通过第 i 对门的某个具体门（左或右）时： * 如果是加法门 (+ a)：会额外产生 a 个新的人。该通道内原先存在的人数不变。 * 如果是乘法门 (x a)：假设该通道在操作前有 P 个人，操作后会变为 P * a 个人。这相当于原有的 P 个人每人变成了 a 个人中的一个“基底”，同时额外新增了 (a-1) * P 个人。

规则核心：在每一对门的操作完成后，所有在这一步新产生的人（无论是加法直接产生还是乘法操作新增的部分）可以被最优地分配到左通道或右通道，以便他们进入下一对门（第 i+1 对门）并获得后续的最大收益。

目标是计算通过所有 n 对门后，左右通道的总人数最多可以是多少。

二、分析

核心在于，已在通道内的人不能改变路径，但新产生的人可以灵活分配。加法门直接产生新人，乘法门在倍增原有人的同时也可以视为产生了新增的人（即 (因子-1) * 原有人数）。我们需要合理地分配所有这些新增的人，以最大化他们通过后续乘法门能带来的总人数。
第一阶段：反向DP计算“未来潜力”或“等效乘数”
我们从后向前计算 l[i] 和 r[i]。
* l[i]：定义为，若有1单位的人从第 i 对门的左门进入，假设之后所有新产生的人都进行最优分配，那么到游戏结束时，这个人（连同他引发产生的所有人）能产生的最大总人数。
* r[i]：类似定义，针对从第 i 对门的右门进入的情况。

第二阶段：正向模拟游戏过程，利用“未来潜力”做决策
在计算出所有 l[i] 和 r[i] 后，我们从第 0 关开始，模拟游戏进程：
* 维护当前左通道人数 people_l 和右通道人数 people_r（初始均为1）。
* 对于第 i 对门：
* 首先，根据乘法门的操作，更新 people_l 和 people_r 的基数（即通道内原有的人数倍增）。
* 然后，计算当前第 i 对门的左右两门总共新产生了多少人（这些新产生的人包括加法门直接给的，以及乘法门在原有基数上额外增加的部分 (因子-1)*基数）。
* 将这些所有新产生的人，根据下一阶段（即从第 i+1 对门开始）的“未来潜力” l[i+1] 和 r[i+1] 进行比较，统一分配到潜力更大的那个通道中，更新相应的 people_l 或 people_r。

三、边界条件

l[n] = 1
r[n] = 1

虚拟出第n + 1关，由于n + 1不存在门，所以倍率为1。

四、计算方式

l[i] = l[i + 1] + (a - 1) * max(l[i + 1], r[i + 1])
r[i] = r[i + 1] + (a - 1) * max(l[i + 1], r[i + 1])

若第 i 关的左门是乘法门 x a：
l[i] = l[i+1] + (a - 1) * max(l[i+1], r[i+1])
l[i+1]：代表最初进入左门的那1个人，如果他继续沿着左通道走到底，他自身能产生的最终等效人数。
(a-1)：代表因为这个乘法门，额外“凭空”多出来了 a-1 个和最初那个人有相同潜力的人。
* max(l[i+1], r[i+1])：这 a-1 个新增的人中的每一个，都会被智能地分配到下一关（i+1）开始时潜力更大的那条通道（左或右）去继续“增值”。

若第 i 关的左门是加法门 + a：
l[i] = l[i+1]
* 因为加法门不改变从它这里通过的“1个人”的未来增值特性，这个人的潜力完全由下一关决定。（加法门产生的 a 个新人是在第二阶段正向模拟时才考虑分配的。）

t = int(input())
for _ in range(t):
    n = int(input())
    left = []
    right = []
    for _ in range(n):
        a = input().split()
        left.append([a[0], int(a[1])])
        right.append([a[2], int(a[3])])
    l = [0] * (n + 1)
    r = [0] * (n + 1)
    l[n] = 1
    r[n] = 1
    for i in range(n - 1, -1, -1):
        if left[i][0] == '+':
            l[i] = l[i + 1]
        else:
            l[i] = l[i + 1] + (left[i][1] - 1) * max(l[i + 1], r[i + 1])
        if right[i][0] == '+':
            r[i] = r[i + 1]
        else:
            r[i] = r[i + 1] + (right[i][1] - 1) * max(l[i + 1], r[i + 1])
    l_people = 1
    r_people = 1
    l_new = 0
    r_new = 0
    for i in range(n):
        if left[i][0] == '+':
            l_new = left[i][1]
        else:
            l_new = l_people * left[i][1] - l_people
        if right[i][0] == '+':
            r_new = right[i][1]
        else:
            r_new = r_people * right[i][1] - r_people
        if l[i + 1] > r[i + 1]:
            l_people += l_new + r_new
        else:
            r_people += l_new + r_new
    print(l_people + r_people)