[AGC036F]Square Constraints

我觉得我的认知出现了问题。
看到这道题就想到容斥,因为如果所有限制只有一端的话可以排序之后直接统计。(如果排序之后第i小的区间长度为$a_i$,那么答案为$\prod_{i\ge 1} (a_i-i+1)$)
我当时认为容斥哪一端都一样。所以就选择容斥下界。那么每个元素有两种选择,且分别递增,而且后n个位置的右端点都大于等于前n个最大的左端点。
我们要dp的话显然不能状压,所以每个决策必须唯一。因此我们可以将$P_i$值域分为三块,前n个位置左端点在第二块,右端点在第三块。后n个位置左端点在第一块,右端点在第二块。
我们直接排序第二块,然后进行dp。由于是排名而且式子很难拆,所以我们必须先枚举其中两块分别取的个数,然后dp的时候状态还需要三维,所以总复杂度$O(n^5)$
然后可以发现后n个位置都是左端点都是0,那么可以将$O(n^5)$的dp优化到$O(n^4)$。然后我就自闭了。
最后我face不要地看了一下题解,发现它是反着容斥的,就是容斥上界。这样的话那些0是无用决策,就是后n个决策唯一,那么就可以直接优化到$O(n^3)$了,然后就可以AC了。
这道题说明一些没有证明过的东西不能单凭常识来妄下定论,需要多注意一下。

Tagged with:

发表评论