[AGC017F] Zig Zag

对每条线 DP，从上往下安排折线形态。

因为前一条线对当前的线有限制，所以需要计入状态。即状态应与已分配过的线数 $n$、当前线已安排的行数 $i$、左侧第一条线的形态 $T$，当前线已安排的形态 $S$ 有关。

---

发现状态中存在一些冗余信息：

我们不关心上一条折线 $T$ 第 $i$ 行以上的走势，只关心当前线 $S$ 到 $T$ 在第 $i$ 行上之间的宽度。

---

再次深入考虑后我们发现 $T$ 的第 $i$ 行一下的某一部分我们也不关心。

如果，我们安排当前线以下部分一直向左直到撞到上一条线，至少一直向左的部分长为 $k$，那么折线 $T$ 的第 $i$ 行一下的 $k$ 段，其形态我们也不关心。

---

又想到 $S$ 的长度仅为 $i$，$T$ 中我们只关心 $i$ 以下一直向左走多久会被撞到，和撞到的位置以下 $T$ 的形态，我们可以巧妙地设置状态。

这个状态的意义为，第 $i$ 行及以上部分为当前安排的折线形态 $S$，以下为尽量往左走，能够走出的形态。

这样将复杂度优化到 $O(n^22^n)$。