《算法竞赛宝典》基础算法艺术(公开课程)

【问题描述】穿越时空（Siworae.cpp/c/pas）POJ 1230

李旭琳要回到原来的时空，如图7.4所示，在时空中有一些时空乱流（灰色区域）。时空乱流平行于X轴，宽度为一个单位，但长度各不相同，并且同一区域上不会有两个时空障碍。现在她要从上方沿Y轴方向，走到下方。途中可以穿越部分时空乱流，但会消耗一部分魔法力，所以穿越数有限制，不能超过一个值k。所以，要保证李旭琳无论从X轴哪点出发，都能走到下方，必须湮灭某些时空乱流，使得每条路上的时空乱流数都不超过穿越的限定值。现给定时空乱流的分布与穿越限定值，问至少湮灭多少时空乱流，可保证每条路上的时空乱流数不超过该限定值。例如此图中，当穿越限定值k=3时，李旭琳除了Ｘ轴为６的点外，可以从Ｘ轴的任何一点出发。