邮戳拉力赛

好题啊！

写了一个错误的解，但仍未知道错在哪里。

容易发现路径一定是：向上走，到一个点后向下走，走到一个点后再向上走，以此类推。

往下走时，可以自由选择是下行时盖章还是上行时盖章，这也是一直往上走不最优的理由。

从 \(0\) 向上走到 \(n+1\) 的路径长度可以最后再加，不用考虑。那么我们得到的是一段一段的区间，区间的贡献需要特殊计算。

区间是这么产生的：首先从上行车站转到下行车站，往前走一段后再从下行车站转到上行车站。这实际上就是一对括号。括号有着很好的性质，我们可以用 dp 求解。

设 \(f_{i,j}\) 表示当前转移到 \(i\)，有 \(j\) 个左括号尚未匹配。那么容易从 \(f_{i - 1}\) 转移。

但是还没完。样例一告诉我们可以有多个括号在同一个格子。因此我们还要从自身转移。但这也是不难的，因为这就是一个完全背包。从小到大依次转移即可。

JOIOJI

给你一长度为 \(n\)，只包含 J,O,I 三个字母的字符串，求最大长度的子串，使子串中 J,O,I 三个字符出现次数相同

思考只有两个字母时怎么做。一个经典的转换是把其中一个视为 \(1\)，另一个视为 \(-1\)，那么符合要求的子串和应该为 \(0\)。在实现中，子串和相同就是前缀和相同。

扩展到三个字母也一样。用 map 记录 J,O 与 O,I 的前缀和组成的一对，如果这一对前缀和都相同即为 J,O,I 三者出现次数相同，然后把最左端的与最右端匹配即可。

INFORMACIJE

乐子题，匈牙利算法只清空一边 WA 一发，警钟长鸣。

由于 \(n\) 只有两百，考虑一些暴力的做法。比如，我们对每个点可能赋成哪些值与这个点连边，然后跑二分图匹配。

这样是错的！我们无法保证最大最小值在要求的区间中出现。于是我们必须禁止其他的点选到这个值，然后就过了。

匈牙利算法只清空一边 WA 一发，警钟长鸣。