20 · Snakes · GESP考级

题目描述

设想一个游戏，场地是由 $1 \times 10^9$ 这样的方格组成的长条，每个方格用从 $1$ 到 $10^9$ 的编号表示。 你要在这些方格中放置 $n$ 条蛇（编号为 $1$ 到 $n$）。起初，每条蛇仅占据一个方格，且每个方格不能被多条蛇同时占用。在完成初始放置之后，游戏正式开始。 游戏会持续 $q$ 秒。在每一秒，有两种可能的事件： 蛇 $s_i$ 变长：如果蛇 $s_i$ 占据了方格区间 $[l, r]$，它会向右扩展，变成占据区间 $[l, r+1]$； 蛇 $s_i$ 缩短：如果蛇 $s_i$ 占据了方格区间 $[l, r]$，它会向左收缩，变成占据区间 $[l+1, r]$。 每秒钟只会发生其中一种事件。 如果任何时间点有蛇碰到了障碍物（其它蛇或方格带的边界），你将立刻输掉游戏。否则，你的得分则等于所有蛇所占领的最大方格编号。 你需要在不输掉游戏的情况下，最小化最终得分。

第一行包含两个整数 $n$ 和 $q$，表示蛇的数量和事件的数量（$1 \le n \le 20$；$1 \le q \le 2 \cdot 10^5$）。接下来的 $q$ 行每行描述一个事件。 第 $i$ 行包含： " $s_i$ +"，表示第 $s_i$ 条蛇扩展； " $s_i$ -"，表示第 $s_i$ 条蛇收缩。 给出的事件序列是有效的，即任何长度为 $1$ 的蛇都不会收缩。

输出一个整数，表示你可以取得的最低得分。

输入 #1

3 6
1 +
1 -
3 +
3 -
2 +
2 -

输出 #1

输入 #2

5 13
5 +
3 +
5 -
2 +
4 +
3 +
5 +
5 -
2 +
3 -
3 +
3 -
2 +

输出 #2