POJ 1201 Intervals

首先复习一下差分约束系统建图基本知识:

  • 对于约束条件 a-b \leqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最短路,得到的是最大解。(负环无解
  • 对于约束条件 a-b \geqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最长路,得到的是最小解。(正环无解

我们来观察这个题。

尝试向差分约束去靠拢,那么观察题面,条件是

r_i - l_{i-1} \geqslant c_i

这玩意怎么来的呢? 首先我们把这个题看成“选子集”的问题(一个位置代表一个元素)

套路地,我们设 x_i 是第 i 位置的”值” ( 选中-> 1 未选中-> 0 )

套路地,我们设 s_i 是前 i 位置”值”的前缀和。

那么就可以得出以上的约束式。

并且以这样的转化,我们一定可以建立关系

0 \leqslant s_{i} - s_{i-1} \leqslant 1

这些关系已经够了。但是有个地方很不舒服,就是上面的两个 \leqslant

把式子倒过来:

s_{i} - s_{i-1} \geqslant 0

s_{i-1} - s_{i} \geqslant -1  

做完了。

注意 s_{0-1} 会爆炸所以把所有下标 +1

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据