Luogu – P5994 – [PA2014]Kuglarz

题意

有 $n$ 个杯子排成一行,编号为 $1,2,…,n$,其中某些杯子底下藏有一个小球。

对于任意的 $i\leq j$,题目给定 $c_{i, j}$,表示花费 $c_{ij}$ 元,你就可以知道 $i,i+1,…,j$ 底下藏有球的总数的奇偶性。

求至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?

$1\le n\le 2\times 10^3$,$1\le c_{ij}\le 10^9$.

分析

不能区间DP,时间复杂度都不对。

猜出每个杯子里是否有小球 $\Leftrightarrow$ 知道每个 $[i, i]$ 的奇偶性 $\Leftrightarrow$ 知道每个 $[1, i]$ 的奇偶性。

因为 $i$ 的奇偶性可以通过 $[1, i]-[1, i-1]$ 得到。

花费 $c_{i, j}$ 的代价查询 $[i, j]$ 的奇偶性之后,若我们知道 $[1, i-1]$ 的奇偶性,那么 $[1, j]$ 可以直接计算出。

这并不完全正确,$i=1$ 时,区间 $[1, 0]$ 是不存在的,所以我们把前缀的左端点从 $1$ 改成 $0$。

花费 $c_{i, j}$ 的代价查询 $[i, j]$ 的奇偶性之后,若我们知道 $[0, i-1]$ 的奇偶性,那么 $[0, j]$ 可以直接计算出。

我们在 $i-1$ 和 $j$ 之间连一条权值为 $c_{i, j}$ 的边,表示:在 $[0, i-1]$ 和 $[0, j]$ 二者之中,只要知道一个的奇偶性,花费 $c_{i, j}$ 就可以知道另一个。

那么在这样的图上,$[l, r]$ 连通等价于:已知区间 $[0, l-1]$ 和 $[0, r]$ 的奇偶性。

要选代价一组代价和最小的边,使图连通。

求 $n+1$ 个点的最小生成树即可。

$\rm{Kruscal}$,时间复杂度 $\mathcal{O}(n^2\log n)$.

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();