区间dp
「POI2015」Myjnie-区间dp
· ✏️ 1102 words · ☕ 3 mins read

有 $n$ 家洗车店从左往右排成一排,每家店都有一个正整数价格 $p_i$ 。有 $m$ 个人要来消费,第 $i$ 个人会驶过第 $a_i$ 个开始一直到第 $b_i$ 个洗车店,且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$,那么这个人就不洗车了。

请给每家店指定一个价格,使得所有人花的钱的总和最大。