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$。这是有三个变量的线性规划问题,可以用单纯形法解决此题。

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *