AC. 梦想

frank_c1

[ZJOI 2012] 波浪

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

题意简述

定义一个n元排列P的权值v(P)如下

v(P) = \sum_{i=1} ^ {n-1} {|P_i - P_{i+1}|}

求等概率随机一个n元排列求出的权值\ge m的概率。输出保留q位小数。

n \le 100, m \le 2 ^ {31} - 1, q \le 30

算法讨论

感觉如果不卡常数不卡空间不卡精度的话就是一道十分优美的题了!

先转化为计数问题,最后再除以n!

我们考虑将1n依次加入排列,维护现在排列形成了多少段和现在加入的数对权值的贡献,这明显是可以DP的。

f(i,j,k,s)为考虑到i,已经加入的数对权值的贡献为j,且这些数划分成了k段,且已经有s个数成为了边界。我们来讨论一下ii+1的转移。

首先根据s的取值可以分成三类讨论,因为边界在一定程度上会影响转移的过程,但是总体上是类似的。我们不妨先考虑s=0的情况,再对其他部分适当调整即可。

第一种情况,就是i的加入形成了新的一段。由于有k+1个间隙,转移系数就是k+1。同时新开辟一段的话,i左右的数一定都是比i大的,于是i的贡献就是-2i

第二种情况,就是i的加入延展了原来某段。由于有k段,每段都可以向两边扩展,转移系数是2ki的两边一定是一边比i大而另一边比i小的,于是相互抵消,贡献为0

第三种情况,就是i的加入合并了某两端。由于有k段,只有k-1个合并位置,转移系数就是k-1i的两边都比i小,于是i的贡献是2i

还有就是两种i成为边界的讨论了。边界在最左边或者最右边,所以只存在上述的第一种情况和第二种情况。而由于边界最多2个,所以s=2时是没有这两种转移的。到此我们可以轻易计算出转移总数是13种,认真分类讨论一波就好啦。

最后需要考虑的就是精度问题了。由于复杂度是O(n ^ 4)的,如果写高精度需要非常优秀的常数优化且代码太长。但考虑到精度至多保留30位,我们可以采用__float128类型。然而这个类型内存占用较大且运算较慢,如果全部采用可能会超时。那么我们对精度要求低的点用double,精度要求稍高的就上__float128就可以顺利通过此题了。

如果还有不理解的细节,可以看看我的代码。(我是全程对着学姐的代码膜的Orz

(小小的吐槽:辣鸡卡时间卡空间卡精度毁我青春。