P2854 [USACO06DEC] Cow Roller Coaster S

有 $n$ 条线段，每条线段只能放在数轴上的一个特定位置，并且第 $i$ 根线段有如下几个属性：$X_i$（该线段放在数轴上的起点），$W_i$（该线段长度），$F_i$（你若使用该线段你能获得的价值），$C_i$（你若使用该线段你所需要的费用）。现在让你从中选出一些线段，使得这些线段能够铺满数轴上的区间 $[0,L]$ 且线段必须首尾相接（也就是不能重叠，也不能空缺），并且所花费用和不超过 $B$，同时要使你收获的价值尽量大，请你找到这个方案。

无

无

Taking the 3rd, 5th and 6th components gives a connected roller-coaster with fun value 17 and cost 7. Taking the first two components would give a more fun roller-coaster (25) but would be over budget.