CF377C Captains Mode

Kostya 是一名专注于 Dota 2 项目的职业选手。最近，该游戏的开发商 Valve 发布了一个新补丁，使得游戏的平衡发生了巨大变化。作为队长的 Kostya 意识到，最大的责任在于自己，因此他希望用数学的视角对补丁的创新进行分析，从而在每局比赛中为自己的队伍选择最合适的英雄。 一场 Dota 2 比赛有两支队伍，每支队伍都需要选择一些英雄，由队员操控，并且不允许多次选择相同的英雄，即使是在不同的队伍中。在 Kostya 所参加的大型电子竞技赛事中，比赛采用“队长模式”。在这种模式下，队长需要按特定的顺序进行两种操作之一：选人（pick）或禁用（ban）。 - 选一个英雄归入本队。被选中的英雄将会被分配给本队（之后会有队员操控），并且该英雄之后无法被任意队伍选择。 - 禁用一个英雄。被禁用的英雄不会被分配给任何一支队伍，但之后同样无法被任意队伍选择。 队长可能会错过一次选人或禁用操作。如果他错过选人，则从当前可选的英雄中随机分配一个英雄到本队；如果错过禁用，则什么都不发生，等同于没有禁用。 Kostya 已经根据最新补丁分析出了所有英雄的强度。当然，Kostya 也知道每一步选人和禁用的顺序。一个队伍的强度为该队伍所有英雄强度的总和。双方队伍都希望最大化自身与对方之间的强度差距。请帮助 Kostya 判断，到底是第一支队伍还是第二支队伍能够在比赛中占据优势，以及该优势的大小是多少。

第一行包含一个整数 $n$（$2 \leq n \leq 100$）—— Dota 2 英雄的数量。 第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \leq s_i \leq 10^6$），表示每个英雄的强度。 第三行包含一个整数 $m$（$2 \leq m \leq \min(n,20)$）—— 队长需要执行的操作次数。 接下来的 $m$ 行，每行格式为 "action team"，表示本步操作。$action$ 仅为 "p"（选人）或 "b"（禁用），$team$ 为需要进行操作的队伍编号（$1$ 或 $2$）。 保证每支队伍至少有一次选人操作，并且每支队伍的选人和禁用次数相等。

输出一个整数，表示当两支队伍都采取最优策略时，第一支队伍与第二支队伍的强度差值。

由 ChatGPT 5 翻译