描述 Description
农夫 John 准备扩大他的农场, 他正在考虑 N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足 (1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积, 但 FJ 可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果 FJ 买一块 3x5 的地和一块 5x3 的地, 则他需要付 5x5=25. FJ 希望买下所有的土地, 但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.
输入格式 InputFormat
第 1 行: 一个数: N
第 2..N+1 行: 第 i+1 行包含两个数, 分别为第 i 块土地的长和宽
输出格式 OutputFormat
第一行: 最小的可行费用.
样例输入 SampleInput
10
811 1153
781 1932
1367 399
1213 1212
1910 54
194 616
1382 1367
1186 632
975 1651
1215 621
样例输出 SampleOutput
2773164
斜率优化 DP。
用 \(l[i]\) 表示长，\(w[j]\) 表示宽。
原始方程： \[ f[i]=Min\{f[j]+l[j+1]*w[i]\} \]
设 \(k<j<i\) 且对于 \(i\) 而言 \(f[j]\) 优于 \(f[k]\)
则
\[ f[j]+l[j+1]*w[i] < f[k]+f[k+1]*w[i] \]
整理得： \[ \frac{f[j]-f[k]}{l[k+1]-l[j+1]}<w[i] \]
于是用斜率优化来搞就好了。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll maxn=50005;
ll i,j,t,n,m,l,r,k,z,y,x;
pair <ll,ll> a[maxn],b[maxn];
ll f[maxn],q[maxn];
ll head,tail;
inline bool comp(pair<ll,ll> a,pair<ll,ll> b)
{
return (a.first==b.first)?(a.second<b.second):(a.first>b.first);
}
inline ll fracup(ll x,ll y)
{
return f[x]-f[y];
}
inline ll fracdown(ll x,ll y)
{
return b[y+1].first-b[x+1].first;
}
int main()
{
scanf("%lld",&n);
for (i=1;i<=n;i++) scanf("%lld%lld",&a[i].first,&a[i].second);
sort(a+1,a+n+1,comp);
m=0;
for (b[++m]=a[1],i=2;i<=n;i++) if (a[i].second>b[m].second) b[++m]=a[i];
head=tail=0;
q[head]=0;
for (i=1;i<=m;i++)
{
while (tail>head && fracup(q[head+1],q[head])<b[i].second*fracdown(q[head+1],q[head])) head++;
t=q[head];
f[i]=f[t]+b[t+1].first*b[i].second;
while (tail>head && fracup(q[tail],q[tail-1])*fracdown(i,q[tail])>fracup(i,q[tail])*fracdown(q[tail],q[tail-1])) tail--;
q[++tail]=i;
}
printf("%lld\n",f[m]);
return 0;
}