P3592[POI2015]MYJ要求总和最大，有两张思路：贪心和dp。稍微想一下，发现贪心思考量太大，考虑dp观察n的数据范围，以及转移方式，可以想到区间dp发现转移跟区间最小值有关，设\(f_{l,r,k}\)为区间\([l,r]\)中最小值不小于\(x\)的答案。转移枚举最小值的位置\(p\)，\(f_{l,r,k}

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

首先不难发现最终答案中只会出现\(c_i\)中的数，所以可以将\(c_i\)离散化。设\(f_{i,j,k}\)表示区间\([l,r]\)，最小值不小于\(k\)的最大收益，\(cnt_{i,j}\)表示区间

P3592[POI2015]MYJ洗车店点击查看代码//此题与人的区间[a,b]有关:区间DP;将[l,p-1],[p+1][r]的区间递归计算,经过p的区间//f[l][r][k]表示l<=a<=b<=r的洗车店的价