1 条题解
-
0
考察内容:动态规划,贪心,随机化
20pts
对于 ,枚举 ,直接计算所有三元环最大的权值。
因为对于三元环而言相对顺序不会改变环的形态,所以只需要枚举的三元点对是 个,在 的情况下可以通过。
另外20pts
对于 ,容易观察到环上的点一定是 最大或最小的若干个点。
枚举所有可能的情况,即去枚举最小的 个最大的 个元素,然后 枚举他们的相对顺序,计算所有情况中的最大值,单组数据的复杂度为 。
100pts
先考虑这么一个问题,找到一条长度为 的路径,,且满足 ,最大化这条路径的长度。
$|x_1-x_2|+|y_1-y_2|=\max(x_1+y_1-x_2+y_2,x_2+y_1-x_1-y_2,x_2+y_2-x_1-y_1,x_1+y_2-x_2-y_1)$
我们将一个点拆分为 种情况 。
我们会发现对于 个点,若前一个点选了第一种情况,第二个点就要选第四种情况。
对应地,需要选 ,上述曼哈顿距离即为这四种情况中的最大值。
因为我们最后要求解的就是一条长度为 的最大路径,所以可以等效为下面这个问题。
每个点都有 项权值,你需要找到一条长度为 的路径,并给每两个相邻点赋 项权值中的某一项,且他们的方案只能是 中的某一种。
那么可以用下面这样一种DP方式, 表示考虑了前 个点,当前路径长度为 ,且最后一个点和下一个点的方式为 中的某一种时,它的最大权值。
再考虑这么一个问题:
找到一条长度为 的环,,且满足 ,最大化这个环的长度。
会发现 和 之间还有一条连边,我们在原来的基础上再加一维,记录 的方式为 中的某一种,在考虑 时补全这一项。
现在回到原问题,我们发现如果最优解最终满足 的话,我们套用上述方式已经求解出了答案,但现在最优解不一定满足这个条件。
我们思考一下如果序列随机,一个大小为 的环有 种拆分方式,且从左往右和从右往左是不影响这个环的形态的,即有 的概率用上述方式得到答案。
我们考虑随机打乱整个序列多次,然后将所有解取最优值,当 时概率为
而
正确率足够高,也可以提高随机次数获得更高的正确率。
整体复杂度为 ,其中 为随机次数。
- 1
信息
- ID
- 160
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者