P9728 [EC Final 2022] Dining Professors

庞教授邀请了 $n$ 位教授参加他的宴会。教授们坐在一个圆桌周围。对于所有 $i$，从 $1$ 到 $n$，教授 $i$ 坐在教授 $(i \bmod n) + 1$ 和 $((i + n - 2)\bmod n) + 1$ 旁边。 庞教授准备了 $n$ 道菜。桌子上有 $n$ 个位置。位置 $i$ 在教授 $i$ 的前面。教授 $i$ 只能接触到放在位置 $i$、$(i \bmod n) + 1$ 和 $((i + n - 2)\bmod n) + 1$ 处的菜。庞教授将在每个位置上放置一道菜。 在这些菜中，有 $a$ 道是辣的，$n-a$ 道是不辣的。有些（可能为 $0$）教授不能吃辣的食物。如果一位教授可以吃辣的食物，他/她的**满意度水平**是他/她可以接触到的菜的数量（无论是辣的还是不辣的）。如果一位教授不能吃辣的食物，他/她的满意度水平是他/她可以接触到的不辣的菜的数量。 庞教授知道每位教授是否可以吃辣的食物。请帮助他安排桌子上的菜，使得所有教授的满意度水平之和最大化。输出最大的总和。

无

无