洛谷 P3336 [ZJOI2013]话旧

图是洛谷搞的

做点简单的观察发现，每一次下降必须经过零点。

对于每个点，有两种状态，从上面走过来，记为下降；从下面走过来，记为上升。

\((0,0)\) 我们记为下降。

设 \(f_{i,0/1}\) 表示前 \(i\) 个点，这个点的状态是上升/下降时的方案。

转移分为 \(5\) 种。

1. \(i\) 号结点和 \(i-1\) 号结点所在直线斜率为 \(1\)。

   显然 \(f_{i,0}=f_{i-1,0}+f_{i-1,1}[y_{i-1}=0]\)。

2. 斜率为 \(-1\)。

3. 过 \(i,i-1\) 点分别作斜率为 \(1\) 和 \(-1\) 的直线，交点在 \(x\) 轴上方，一个倒着的 \(v\) 字形。

4. 交点在 \(x\) 轴上，有两种走法。

5. 为一个倒着的等腰梯形的下部分。先求出中间那段长度 \(l\)。

   每一个中间位置可以向上凸起，左边那个点也要分类讨论，方案数是一个二的次幂。

第二问其实是贪心，解一个方程就好。

注意要判断是否能到达终点。