1 条题解
-
0
题目分析
20pts
表示 的情况下,填入 序列的前 项的方案数。
那么 可以转移到 当且仅当 ,假设值域为 ,时间复杂度为 。
40pts
首先直觉告诉我们合法方案数不好求,所以正难则反考虑求不合法的情况,不合法的情况也不好求,但是我们可以比较自然地想到容斥。
也就是求 表示至少有 个坏点的方案数。
然后考虑动态规划,设 表示前 项划分成 部分,部分内部是相同的数字,但是相邻的部分不要求不同(因为你是容斥,保证至少多少个不同即可)。
显然 。
我们发现这个东西和最小值有关系,一个部分的取值方案就是最小值,这点比较显然。
转移为
$$f_{i,j}=\sum_{k=1}^{i-1} f_{k-1,j-1} \times \min_{x=k}^j a_x$$时间复杂度为 。
60pts
我们并不关心 的具体大小,只关心 的奇偶性,因为容斥系数为 ,所以每取一段,就让方案数乘上 ,我们可以忽略掉 这一维
$$f_{i}=\sum_{k=1}^{i} -f_{k-1} \times \min_{x=k}^j a_x$$时间复杂度为 。
100pts
考虑怎么维护 ,可以维护单调栈的具体形态,利用前缀和在单调栈变化时进行 DP 转移,时间复杂度为 。
- 1
信息
- ID
- 139
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者