本文主要是介绍DTOJ 4844. 数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
联测题不方便写出来。
题解
原本的想法是先按照 B B B降序排序， 把 i i i套进 j j j看作 i i i连到 j j j的一条有向边，这样每个点能连到的点就是一段前缀，求所有极大的连边方案数。但这样由于前缀长度不是单调的，DP时难以用多项式的效率记录状态。
考虑如何使前缀长度单调，即连出边的点按照 A A A从大到小考虑，被连边的点依然按照 B B B从大到小排序（即把每个点拆成两个点，由于原来的边是有向的，且拆点后只能由一边连向另一边，故没有影响，且比较方便）。方案是极大的，等价于所有没有连出边的点，所能连到的前缀都已经被连。根据单调性，枚举最后一个没有连出去边的点，前面的点可连可不连，后面的点一定要连，且要拿出一些连到前面没有被连的点，前后分别用一个DP计算即可。
这篇关于DTOJ 4844. 数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
