小 P 准备了一次预测活动，每个参与活动的人都可以在 PPP 队获胜，GGG 队获胜和平局三种结果中选择自己要预测的一种。如果第 \(i\) 个人预测正确，那么小 P 需要付给他 \(a_i\) 元，否则他需要给小 P 付 \(b_i\) 元。小 P 目前已经收到了 \(n\) 个人报名参加活动的信息，并知道他们每个人选择的结果与对应的 \(a_i,b_i\)，现在小 P 可以任意选择是否允许某个人参加活动，他希望知道最坏情况下他能赚到的钱最多是多少。
\(n \leq 300, a_i, b_i \leq 300\)
假设 \(A_1, A_2, A_3\) 是三种情况中赢得比赛要付的钱， \(B_1, B_2, B_3\) 是输掉比赛要付的钱，那原题即要求:
\[\max\{ \min(B_1+B_2-A_3, B_1+B_3-A_2, B_2+B_3-A_1) \} \]这是一个最大值最小的一个问题，但如果我们考虑二分答案后就会发现这个东西没法做了，因为对于里面的任意一个式子，他和 \(c_i=1,c_i=2,c_i=3\) 的三个状态都有关，我们无法在 \(dp\) 中低复杂度记录这些信息
我们现在想要干什么？我们现在想要对于 \(c_i\) 相等的情况互相独立，因此我们考虑化简一下式子：
\[\begin{align} & \max\{ \min(B_1+B_2-A_3, B_1+B_3-A_2, B_2+B_3-A_1) \} \\ =& \max\{ \min(B_1+B_2+B_3-A_3-B_3, B_1+B_2+B_3-A_2-B_2, B_1+B_2+B_3-A_1-B_1) \} \\ =& \max\{ B_1+B_2+B_3-\max(A_1+B_1, A_2+B_2, A_3+B_3) \} \\ \end{align} \]我们发现这么一番转变后里面的式子里 \(c_i\) 相等的部分就被分开了，因此我们就可以分开 \(dp\) 了
具体的，对于 \(c_i\) 相等的部分我们直接 \(01\) 背包处理，设 \(dp_{o,i}\) 表示选了 \(\sum\limits_{c_j=o} a_j+b_j = i\) 的人时 \(\sum b_j\) 最大是多少。统计答案时可以枚举一个 \(l = \max(A_1+B_1, A_2+B_2, A_3+B_3)\) ，更新答案为 \(ans \leftarrow \max\limits_{i=0}^{l}{dp_{1,i}} + \max\limits_{i=0}^{l}{dp_{2,i}} + \max\limits_{i=0}^{l}{dp_{3,i}} - l\)
标签：limits,min,max,4179,qbxt,block,我们,dp,式子 From： https://www.cnblogs.com/fox-konata/p/17724507.html