Tony Zhao

题目大意

给你N块农田，每块农田都有自己的长和宽，FJ可以每次购买其中的K块农田，购买这K块农田所需要的价格就是这K块农田里面最大的长和最长的宽的乘积。问FJ用最优方案购买所有的农田所需要的最少价钱。

开始学斜率优化DP辣！

好我们首先拿到了这道题~发现这道题求的是方案，所以我们考虑DP。

我们首先假设这样一个特殊情况。如果一块农田正好可以“吃掉”另一块（这块地的长比另一块大，宽也比另一块大）此时我们想如果求最优直接把它们两个绑定，即删掉“被吃的”不就可以了嘛QwQ所以我们Sort一下，删除所有没有任何必要的农田。

此时我们得到了一个按土地长升序（这样规定，降序也可）的土地排列。此时我们想，宽会是怎样排列的呢？

当然是降序的。如果出现了升序或者相等，此时绝对保证前面的可以被后面的吃掉。此时我们就要把前面的删掉。

此时我们获得了拥有优秀性质的土地排列，便于进行DP。

易知（我不会证）我们必须选取连续的区间。

我们设f[i]为买前i块土地的最小花费，那么我们有$f[i]=min(f[j]+l[j+1].y*l[i].x)(0 \lt j \lt i)$.

此时复杂度$O(n^2)$

所以我们需要下降时间复杂度，斜率优化派上了用场。

我们列出$y=kx+b$的方程$f[j]=x[i]*(-y[j+1])+f[i]$

其中y仅包含j，k仅包含i，x仅包含j，b仅包含i，之后我们就可以用一个单调队列维护一下这些值所成的直线，我们通过斜率k进行维护然后就可以O(1)求出每个DP值。

时间复杂度O(n).

#include <cstdio>
#include <algorithm>
using namespace std;
int n,cnt,h,t;
long long q[500010],f[500010];
struct land{
    long long x,y;
}l[50010];
bool cmp(land tx,land ty)
{
    if(tx.x==ty.x) return tx.y<ty.y;
    return tx.x<ty.x;
}
double slop(int a , int b)
{
    return (double)(f[b]-f[a])/(l[a + 1].y-l[b + 1].y);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld%lld",&l[i].x,&l[i].y);
    sort(l+1,l+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        while(cnt&&l[cnt].y<=l[i].y) cnt--;
        l[++cnt]=l[i];
    }
    for(int i=1;i<=cnt;++i)
    {
        while(h<t&&slop(q[h],q[h+1])<l[i].x) ++h;
        f[i]=f[q[h]]+l[q[h]+1].y*l[i].x;
        while(h<t&&slop(q[t],i)<slop(q[t-1],q[t])) --t;
        q[++t]=i;
    }
    printf("%lld",f[cnt]);
}
//f[j]=x[i]*(-y[j+1])+f[i]

BZOJ 1597 土地购买

题目大意