Mayflyyh
Mayflyyh
MayFlyyh's Blog

差分约束
文章归档

POJ 1201 Intervals

题意:给m个区间li,ri,再给一个ci,要求在每个区间li-ri种至少选ci个数,求满足条件最小选的数字。 数字值域:0~50000,m<=50000 哎,考虑差分约束,设D[i]表示从0-i满足条件至少选多少个 l-r,至少选C个,即D[r]-D[l-1]>=c,从l-1到r连一条权值为c的边 然…

   185   2018-08-11 去围观