前言原来是喜欢出背景题的出题组着实有点意思。分析关键结论任意区间的最高评价都等于该区间所有风味值之和因此答案就是整个序列的总和与如何划分以kkk无关。设区间长度为mmm最大风味值为Mmax⁡l≤i≤rai.M\max_{l\le i\le r}a_i.Mmaxl≤i≤r​ai​.。选择值为MMM的甜点作为主打则因为ai≤Ma_i\le Mai​≤MwpmM−∑ilr∣ai−M∣mM−∑ilr(M−ai)∑ilrai.\begin{aligned} w_p mM-\sum_{il}^{r}|a_i-M|\\ mM-\sum_{il}^{r}(M-a_i)\\ \sum_{il}^{r}a_i. \end{aligned}wp​​mM−il∑r​∣ai​−M∣mM−il∑r​(M−ai​)il∑r​ai​.​另一方面对任意选择的主打值xapxa_pxap​单个aia_iai​的贡献为$x-|a_i-x|\le a_i,$所以$w_p\sum_{il}^{r}\left(x-|a_i-x|\right)\le \sum_{il}^{r}a_i.$因此$f(l,r)\sum_{il}^{r}a_i.$无论划分成哪 (k) 个连续非空区间总评价都是$\sum_{j1}{k}f(l_j,r_j)\sum_{i1}{n}a_i.$说白了就是直接求和即可得到答案也算是比较水的一道签到题了。