[hdu6717][百度之星2019]Min

这个题考试的时候完全没有思路,考完之后也没有思路,后来忍不住瞄了一眼题解就发现我会了。说明我太菜了。
题目条件等价于$min(a_{p_i},a_{p_{i+1}})\le a_{p_{i+2}}$
首先考虑所有$a_i$互不相同的情况,我们考虑从小到大将元素插入排列,考虑下一次还能插入的位置。如果没有插入在末尾,那么下一次还能插入的位置一定减少1,如果插在了末尾,那么下一次还能插入的位置就会增加1。
这个结论的证明很容易,我们只需要分类讨论就可以了。但是我一直发现不了这个结论,关键是要寻找一个变化非常有规律的属性,只要想到了“下一次还能插入的位置”这个变量,这道题基本上就解掉了。
有了这个结论,我们可以轻松得到一个$O(n^2)$的DP。
那么$a_i$不同的情况我们只需要一起考虑$a_i$相同的元素,暴力枚举有几个插在前面,有几个插在末尾,然后使用组合数进行转移即可。
注意组合数要预处理,不然会TLE。

Tagged with:

发表评论