为了更好的阅读体验，建议到我的博客查看
对于类似\(dp[i]=max(dp[j]+W_i+W_j+W_i‘W_j‘+C)\)的转移方程（\(W_i,W_i‘\)为与\(i\)有关的参数，\(W_j,W_j‘\)为与\(j\)有关的参数，\(C\)为常数），可以通过单调性来优化
对于\(dp[k]\)，设\(F(x)=dp[x]+W_k+W_x+W_k‘W_x‘+C\)，我们假设\(dp[k]=max(F(i),F(j)),(i<j<k)\)
假设\(F(i)<F(j)\)，那么有\(dp[i]+W_i+W_k‘W_i‘<dp[j]+W_j+W_k‘W_j‘\)
稍微化简一下，得
\((dp[j]+W_j)-(dp[i]+W_i)>W_k‘(W_i‘-W_j‘)\)，假设\(W_i‘-W_j‘<0\)（大于零则不等号不需改变）
则有
\(\frac{(dp[j]+W_j)-(dp[i]+W_i)}{W_i‘-W_j‘}<W_k‘\)
注意：若得到的\(W_k‘\)不具有单调性，不可使用此方法！
令\(G(x)=dp[x]+W_x,H(x)=-W_x\)，则
显然，\((1)\)与斜率十分相似，该方法因此得名"斜率Dp"。
如图所示，假设\(dp[k]\)可以转移自三个点\(A,B,C\)，且\(k2<k1\)。
考虑一下三种情况
对于情况1，根据\((1)\)可知\(A\)点最优，同理，情况2时有\(A\)或\(C\)点最优，情况3时\(C\)点最优。无论如何\(B\)不可能为最优点，因而可以去除。
那么在继续引入任意个点后，有无可能使得\(B\)为最优点呢？
如图所示，在引入新的点后，我们假设\(B\)点为最优点，那么说明此时\(W_D‘>k1\)
又因为\(k1>k2\)，所以\(W_D‘>k2\)，因此\(C\)点优于\(B\)点，与假设不符。
通过上述做法，我们能够得到一个下凸包（斜率单调递增，一般使用队列来维护）。对于给定的\(W_k‘\)，只需要寻找线段\(AB\)，使得该线段为队列中第一段满足斜率\(sloop_{AB}\ge W_k\)的线段，一般可以使用二分法来解决。
特别的，对于\((1)\)，若\(W_k‘\)单调递增，又因为维护的队列中斜率也是单调递增的，则可以通过把队头中\(sloop<W_k‘\)的线段全部弹出，之后队头元素即为最优点。
总结一下，维护的凸包是上凸还是下凸，取决于不等号：
首先，设长方形\(i\)的面积为\(A_i\)，宽为\(W_i\)，高为\(H_i\)，约定\(W_i\ge H_i\)，所有长方形的面积之和为\(S_A=\sum A_i\)，所有长方形的宽之和为\(S_W=\sum W_i\)。
若选定两个长方形\((i,j)(i\ne j,W_i\ge W_j)\)作为两侧的边界，设得到的容积为\(V_{ij}\)，则有
之所以是大于等于而非等于，是因为容器内可能存在比两侧长方形更高的长方形（即存在\(x\not\in\{i,j\}, H_x>W_j\)），但此类方案不可能为最优解，因而不影响最终结果。
得到上述面积公式后，可以把长方形按\(W_i\)降序排列（升序也行，只不过公式稍微复杂一些）
按照斜率Dp的做法，可以得到如下式子
\(\frac{A_i-A_j}{W_i-W_j}<W_k\ (i<j<k) \text{若k从j转移优于从i转移}\)
转移时，二分查找最优转移点即可。
AC代码如下:
#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;
using pll = pair<ll, ll>;
const int maxn = 3e5 + 1000;
ll n, sum_area = 0, sum_width = 0;
pll box[maxn];
int que[maxn], tail = 0;
ll bin_search(ll l, ll r, std::function<bool(ll)> check){
ll result = l, mid;
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)){
result = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
return result;
}
inline ll area(int p){return box[p].first * box[p].second;}
ll get_ans(int i, int j){
if(box[i].first < box[j].first) swap(i, j);
return box[j].first * (sum_width - box[i].first - box[j].first) - sum_area + area(i) + area(j);
}
ll k;
bool check(ll mid){
return (box[que[mid]].first - box[que[mid + 1]].first) * k >= area(que[mid]) - area(que[mid + 1]);
}
void solve(){
cin >> n;
for(int i=1; i<=n; i++) {
cin >> box[i].first >> box[i].second;
if(box[i].first < box[i].second) swap(box[i].first, box[i].second);
sum_area += area(i);
sum_width += box[i].first;
}
sort(box + 1, box + 1 + n, [](pll a, pll b){
if(a.first != b.first) return a.first > b.first;
return a.second > b.second; // 第二关键字随意
});
ll ans = 0;
for(int i=1; i<=n; i++){
k = box[i].first; // 即W_k‘
if(tail > 0){
ll pos = 0;
if(tail > 1){
pos = bin_search(0, tail - 2, check);
if(check(pos)) pos++;
}
ans = max(ans, get_ans(que[pos], i));
}
while(tail > 1 && (area(que[tail-1]) - area(i)) * (box[que[tail-2]].first - box[que[tail-1]].first)
<= (area(que[tail-2]) - area(que[tail-1])) * (box[que[tail-1]].first - box[i].first)) tail--;
que[tail++] = i;
}
cout << ans << ‘\n‘;
}
signed main(){
Android;
solve();
}
原文：https://www.cnblogs.com/lalalachg/p/dynamic_programing_sloop.html