例题：
洛谷P2900 [USACO08MAR]Land Acquisition G
分析与转化
可以发现，有一些东西是完全没用的
当一个矩形的长和宽都比另一个矩形小的时候，这个矩形就是废的，因为他完全可以套在另外那个矩形一起买
这时候我们就能发现：我们得到了一个长度递减，宽度递增的矩形序列
而要求的就是使得在其划分出一些段之后，总代价最小
于是乎我们可以列出方程（显然这是dp）：
$ dp_{i} = max (dp_{j} + w_{j+1} \times h_{i}) $
于是我们就能够 $ O (n^2) $ 的解决了
套用斜率优化
划重点：
斜率优化通用式子:
$ b = y - kx $
其中 \(b\)是我们想要知道的，\(y,x\) 都为前面的“转移项” \(k\) 为当前要求的“特有”的系数
我们必须要保证x是递增的，k随意，b我们这里希望他最小
我们观察式子，发现只有一个项与 \(i\) 和 \(j\) 都有关
于是我们令：
\(x=-w_{j+1}\) （为了保证递增）
\(y=dp_{j}\)
\(k=h_{i}\)
\(b=dp_{i}\)
可以发现，我们这样设完了以后，就能够把转移看作：
在一个二维数点当中，有一条直线已经定了斜率，要求截距最小
如图：
所以我们就能够通过维护下凸壳，并在下凸壳上二分来求得转移位置了
补充
还有一个情况，当你化成二维数点以后要求截距最大
这时候你就需要维护上凸壳
于是上下凸壳的区分就是这么来的
代码实现
补充：有时候h不一定像这样单调的，所以必须二分，一下是兼容性比较强的代码（板子）：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e4+10;
struct modify {
ll w,h;
};
modify a[N],c[N];
bool cmp(modify x,modify y) {
if(x.w==y.w) return x.h>y.h;
else return x.w>y.w;
}
int n,cnt;
ll dp[N];
/*
define:
x: -w_{j+1}
k: h_{i}
y: dp_{j}
b: dp_{i}
*/
int st[N],sttop;
int find(ll k) {
int l=1,r=sttop-1,res=sttop;//注意边界
while(l<=r) {
int mid=(l+r)/2;
if((dp[st[mid+1]]-dp[st[mid]])>=k*(-c[st[mid+1]+1].w+c[st[mid]+1].w)){//二分&&除法转乘法
res=mid;r=mid-1;
} else {
l=mid+1;
}
}
return st[res];
}
int main() {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i].w>>a[i].h;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) {
if(a[i].h>c[cnt].h)
c[++cnt]=a[i];
}
st[++sttop]=0;//注意边界
for(int i=1;i<=cnt;i++) {
int j=find(c[i].h);
dp[i]=dp[j]+c[j+1].w*c[i].h;//按照原来的方程转移（切记不要直接用x，y）
while(sttop&&
(dp[st[sttop]]-dp[st[sttop-1]])*(-c[i+1].w+c[st[sttop]+1].w) >
(dp[i]-dp[st[sttop]])*(-c[st[sttop]+1].w+c[st[sttop-1]+1].w))//同样
sttop--;
st[++sttop]=i;
}
cout<<dp[cnt];
return 0;
}
于是这题就完成了
题目总结
-
把原来方程转化为上述式子，使得：x递增（关键！！）
-
在二分和推单调栈的时候，一定要手画出边界，不然会错
-
涉及除法判断时，尽可能转
long long，避免丢精度