AC. 梦想

frank_c1

[ZJOI 2013] 话旧

发布于2017年03月01日 | 暂无评论 | 449阅读 | 动态规划

题意简述

有一个长度为n+1的序列A_0, A_1, ..., A_n,满足下列条件。

1. A_0 = A_n = 0

2. 对于0 \le i \le n - 1|A_i - A_{i+1}| = 1

3. 对于所有极小值点k,有A_k = 0

我们还规定了Am个位置的值。

求满足条件的序列个数 和 序列最大值的最大值。第一问的答案对19940417取模。

1 \le n \le 10 ^ 9, 0 \le k \le 10 ^ 6

算法讨论

首先要看清题呐。第一眼看成了最小值了,于是A掉了3216……

一个显然的思路是按关键点分段。

我们想,如果两段之间相互独立那是再好不过了,然而现实是残酷的,怎么可能呢?

考虑什么因素让它不能相互独立。在其他地方我们都可以控制极小值必须为0,但是唯独关键点不行,即我们无法控制关键点是否成为了一个极小值点。于是我们考虑设计一个DP来解决这个问题。

f(i,j)为到达i关键点的斜率为j。在本题中j可以取1-1

这样的状态就可以避免在非零关键点产生极小值点。

考虑ii+1的转移,显然可以分成-1 => -1, -1 => 1, 1 => -1, 1 => 1四类讨论。我们设前后两点为A, B

对于-1 => -1,两点都是下行的。情况1就是A直接下行到B。情况2,就是A先下行到0然后经过一段00的过程,再上行到B上方,再下行到B。我们讨论一下这个转移的系数:设00的过程最长可以是m,则贡献是\sum_{i=0} ^ {m/2} {2 ^ {\max(i-1, 0)}} = 2 ^ {m/2}

对于-1 => 1,A点下行,B点上行。这个只有一种情况,即A下行到0,经过一段00的过程,再上行到B。注意这里00的过程是定长的,于是贡献就直接是2 ^ {max(0,m/2-1)}

对于1 => -1,A点上行,B点上行。情况1是中途没有接触到0,都在空中飞,贡献至多为1,判一下成立条件。情况2是A点上行一段,再下行到0,经过一段00的过程,再上行到B上方,再下行到B。考虑贡献怎么算:\sum_{i=0} ^ {m/2} \sum_{j=0} ^ {m/2-i} {2 ^ {\max(0, m/2 - 1 - i - j)}} = \sum_{i=0} ^ {m/2} {2 ^ {m/2 - i}} = 2 ^ {m/2 + 1} - 1

对于1 => 1,两点均上行,和-1 > -1的转移基本对称,就不再赘述。

DP时同时计算两个子问题的答案。还有一点就是写的时候一定要细心细心再细心。这种大讨论题最讨厌了!

时间复杂度O(k \log n)