UOJ Logo kczno1的博客

博客

Codeforces Round #472 E

2018-03-28 10:32:31 By kczno1

最后的盒子一定是前面一段没贡献,中间一段有贡献,后面一段没贡献。

那么$b_{i}=0$的$a_{i}$的作用就是放在前面一段,$dp$求出哪些前缀是可以被他们摆出,然后就可以丢掉他们了。

设将$b_{i}=1$的$a_{i}$排序后为$na_{1},..na_{nn}$

设中间有贡献的那一段为$v_{1},v_{2},..v_{m}$

可以发现,$v_{1},v_{2}..v_{m-1}$一定是$na_{1},na_{2},..na_{m-1}$,而$v_{m}$只要是$na_{m},..na_{nn}$中的一个就可以了。

因为如果有一个是更大的,换成更小的一定不会变劣。

那么我们就从后往前$dp$,$dp_{i,0/1,j}$表示到了第$i$个,是否有$na$没选,能否摆出长度为$j$的前缀。

用$bitset$优化,复杂度$O(n^{2}/32)$

官方题解好像说能$O(n \sqrt{n})$,我不知道怎么做。

(而且我还没看见$O(n \sqrt{n})$的代码,不然我也不能拿下时间$rank1$了)

代码:http://codeforces.com/contest/956/submission/36681265

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。