Expensive Drink

题意概述

已知$0 \le c_1 \le c_2 \le c_3, \ 0 \le c_4, \ L \le a_4c_4 \le R$。$c_1, c_2, c_3, c_4$均为未知的常量。

给出$L, R$和$n$组$a_1, a_2, a_3, p$，对于任意一组均满足$p=a_1c_1+a_2c_2+a_3c_3+a_4c_4$。现在给出一组$a_1, a_2, a_3$，求$p$的最大值。

数据范围：$1 \le n \le 100$。

算法分析

对于每一组$a_1, a_2, a_3, p$，可以列出不等式$p-R \le a_1c_1+a_2c_2+a_3c_3 \le p-L$，其中有三个未知数$c_1, c_2, c_3$。最后要求的答案就是在满足所有约束的情况下$\max(a_1c_1+a_2c_2+a_3c_3)+R$。这是有三个变量的线性规划问题，可以用单纯形法解决此题。