【BZOJ 4498】魔法的碰撞

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4498
神犇题解Ⅰ:http://blog.csdn.net/visit_world/article/details/51090964
神犇题解Ⅱ:http://www.cnblogs.com/wangyurzee7/p/5365710.html

解题报告

如果我们知道了一个排列的最短长度 $w$
那么我们这个序列对于答案的贡献就是 $C_{l – w}^n$
那么如果我们知道最短长度为$w$的排列有$c_w$个,那么答案就是 $\sum\limits_{w = 1}^l {{c_w} \cdot C_{l – w}^n} $

那么现在的问题就是如何求$c_w$了
考虑一个Mogician,其对于答案的贡献有$3$种:$0/d_i/2d_i$
考虑按权值从大到小安排,我们钦定一个Mogician的贡献

如果贡献为$0$,那么两侧都是比他大的,换一句话来说他两侧不能再安排其他膜法师了,于是能安排膜法师的位置减少一个
如果贡献为$d_i$,那么一侧比他大,一侧比他小,能安排膜法师的位置没有变化
如果贡献为$2d_i$,那么两侧都应该比他小,于是能安排膜法师的位置增加一个

这样的话,我们就可以设$f[i][j][k]$表示“考虑到第$i$个膜法师,能安排膜法师的位置有$j$个,当前序列的最短长度为$k$”
然后就可以愉快的转移啦!时间复杂度: $O({n^4} + L)$

—————————— UPD 2017.3.3 ——————————
今天又做到一道类似的题目:BZOJ 4321
题解的话,可以看这里:http://blog.csdn.net/geotcbrl/article/details/49663401

2 thoughts to “【BZOJ 4498】魔法的碰撞”

Leave a Reply

Your email address will not be published. Required fields are marked *