标签:差分约束

4 篇文章

10087. 「一本通 3.4 例 1」Intervals
题意 从$0\sim 5\times 10^4$中选出尽量少的整数,使每个区间$ [a_i,b_i]$内都有至少 $c_i$个数被选出。 思路 当然食用spfa啦。 设s[k]表示0~k中至少选多少个整数。根据题意可得: $$s[b_i]-s[a_i-1]\geq c_i$$ $$s[k]-s[k-1]\geq0$$ $$s[k]-s[k-1]\l…
10088. 「一本通 3.4 例 2」出纳员问题
题意 R(0)、R(1)、R(2)…R(23)表示第x个时刻需要R(x)个出纳员,有n个出纳员申请工作,第i个出纳员从t_i时刻开始工作8小时,问至少需要多少出纳员? 思路 设$x[i]$表示第$i$时刻实际上需要雇佣$x[i]$人,$r[i]$为第$i$时刻至少需要$r[i]$个人。 $$x[i-7]+x[i-6]+x[i-5]+x[i-4]+x…
10089. 「一本通 3.4 练习 1」糖果
题意 满足条件: 如果 X=1.表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的精果一样多。 如果 X=2,表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。 如果 X=3,表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。 如果 X=4,表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。…
10090. 「一本通 3.4 练习 2」布局 Layout
题意 有些奶牛是好基友,它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌,它们希望彼此之间的距离大于等于某个数。 思路 如果两只奶牛是好基友,那么: $$A-B\leq D$$ 如果两只奶牛是情敌,那么: $$A-B\ge D$$ 即: $$D\leq A-B$$ 也就是: $$B-A\leq -D$$ 直接上代码: [crayon-5db07…