题解：P3336 [ZJOI2013] 话旧

_0X7F_ · 2026-05-07 13:22:56 · 题解

P3336 [ZJOI2013] 话旧

题目传送门。

提交记录。

题目思路

这是一道分类讨论动态规划题。

做法

第一问

首先，我们不难观察到一些性质，这对做题有很大的帮助。

函数值一定非负，否则不符合题目极小值为 0 的要求。
函数图像开始下降时，一定下降为 0。
对于 k=0 方案数，此时一共有 \frac{n}{2} 次上升，每一次上升都可以选下降至 0 或继续上升，注意最后一次上升一定要选下降，所以有 2^{\frac{n}{2}-1} 种选法。这一性质至关重要。

然后，我们开始分类讨论。

我们令 dp[i][0] 表示经过第 i 点，上一段线段为斜率为 -1，令 dp[i][1] 表示经过第 i 点，上一段线段为斜率为 1。

不妨考虑通过上一点转移。

dp[i][1] 的状态转移

考虑由 dp[i-1][1] 转移。

两点之间的线段恰好斜率为 1。直接将 dp[i-1][1] 加入 dp[i][1] 中。

点 A 与 y=0 的交点为 C，点 B 与 y=0 的交点为 D。不难发现每条线段之间相差 2，所以 CD 的长度为 2K(0 \le K \le \frac{len}{2})。于是，我们可以列出一个方案数式子：

\sum_{i=1}^{\frac{len}{2}}2^{i-1}+1(len=x_i-x_{i-1}-y_i-y_{i-1})

显然时间复杂度太高，我们需要简化一下：

令 S=\sum_{i=1}^{\frac{len}{2}}2^{i-1}，所以 2S=\sum_{i=1}^{\frac{len}{2}}2^{i}。

2S-S=\sum_{i=1}^{\frac{len}{2}}2^{i}-\sum_{i=1}^{\frac{len}{2}}2^{i-1}=2^{\frac{len}{2}}-2^0

S=2S-S=2^{\frac{len}{2}}-1

所以

\sum_{i=1}^{\frac{len}{2}}2^{i-1}+1=2^{\frac{len}{2}}

运用快速幂迅速求出。

考虑由 dp[i-1][0] 转移。

直接画图理解，不难发现还是对于 k=0 方案数。答案就是 2^{\frac{len}{2}-1} 种，其实就是之前考虑过的状态。

dp[i][0] 的状态转移

考虑由 dp[i-1][0] 转移。

两点之间的线段恰好斜率为 -1。直接将 dp[i-1][0] 加入 dp[i][0] 中，这也是最简单的情况。

考虑下图情况，注意不能直接连接点 B 和 y=0 的直线，因为 dp[i][0] 的上一条线段斜率为 -1。所以此时 len=x_i-x_{i-1}-y_i-y_{i-1}-2，与上文思维相似，不再赘述。方案数为 2^{\frac{len}{2}}。

考虑由 dp[i-1][1] 转移。

若两点之间的线段恰好斜率不为 1。直接将 dp[i-1][1] 加入 dp[i][0] 中。因为若斜率为 1，则不能满足 dp[i][0] 的状态表示。

考虑下图情况，类似的，方案数是 2^{\frac{len}{2}}-1，其中 len=x_i-x_{i-1}-y_i-y_{i-1}。

注意边界条件，以防访问到负数下标。

最后放一个转移方程 (大行公式警告)：

dp[i][0]= \begin{cases} dp[i-1][0] \times 2^{\frac{len-2}{2}} \\ dp[i-1][0] & a[i].x+a[i].y=a[i-1].x+a[i-1].y \\ dp[i-1][1] \times (2^{\frac{len}{2}}-1) \\ dp[i-1][1] & a[i].x-a[i].y \ne a[i-1].x-a[i-1].y \end{cases}

dp[i][1]= \begin{cases} dp[i-1][0] \times 2^{\frac{len}{2}-1} \\ dp[i-1][1] \times 2^{\frac{len}{2}} \\ dp[i-1][1] & a[i].x-a[i].y=a[i-1].x-a[i-1].y \end{cases}

第二问

比第一问简单很多，只需要贪心的选择图像上升情况，最后统计是否合法，取最大值即可。注意不要将不合法答案计入。

最后

一定要注意边界条件，代码不贴了。