jzoj5370

先考虑性质B。
考虑使用"01赋值判定"技巧,计算答案(>x)方法数。
(l_i)排序后,设([a_i,b_i]=(l_i,l_{i+1}]),则如果(x,y)落在第(i)个区间内,则(x,y)的答案是相同的。
枚举(x)落在的区间内,把(>x)的数赋值成(1)(leq x)的数赋值成(0)
考虑dp,设(f_{i,j,k})表示填完前(i)个数,堆内有(j)(0),填了(k)(0)
填的(1),堆内的(1)个数可以通过(j,k)推断出。
在dp时,如果插入了数,则枚举下一个地方填的数(假设所有(0,1)都是不同的)。
如果弹出了数,则显然系数可以通过(b,i)来计算。
弹出的数显然会优先弹(0)
效率(O(n^4)),得分(30)
定义阶段:先进行(1)操作,后进行(2)操作。
考虑把原数组划分成若干段,使得第一段全是(1)操作,有若干个阶段,然后全是(2)操作。

原文地址:https://www.cnblogs.com/ctmlpfs/p/14618636.html