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]\leq1$$ 也就是:
$$s[k-1]-s[k]\geq-1$$
那么跑一次最长路就好了。
暂无评论

发送评论


				
上一篇
下一篇