诡意行商 (roguetrader)
题目描述
坎诺特开了一家商店,商店里共 $n$ 个商品,第 $i$ 个商品卖 $a_i$ 块钱,其价值为 $c_i$。 小鱼人要去商店里买东西。它会按照最优的策略买东西,即如果它有 $x$ 块钱,它会在买的东西需要付不超过 $x$ 块钱的同时 价值和最大。
由于小鱼人很有钱,坎诺特打算坑一把小鱼人。坎诺特会选取一个区间 ,对这个区间里面的商品进行涨价。第 $i$ 个商 品涨价后的价格为 $a_i$。
坎诺特知道小鱼人有不超过 块钱且认为小鱼人的钱数在 $[1,V]$ 中均匀随机。因此坎诺特想知道有多少区间 满足给 内的商品涨价后,小鱼人购买商品价值和的期望不超过 $L$。 输入格式
第一行三个数 。接下来 $n$ 行,每行三个数 $a_i,b_i,c_i$,含义如题目所述。
4 4 2
1 2 1
2 4 2
1 3 2
3 5 3
3