题目描述
农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.
输入描述
* 第1行: 一个数: N
* 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽
输出描述
* 第一行: 最小的可行费用.
输入样例
4 100 1 15 15 20 5 1 100
输出样例
500
提示
【样例说明】
FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和 15x15 . 每组的价格分别为100,100,300, 总共500.
题目分析
BZOJ日常难题，看到FJ就知道是USACO了。
①算法确定
二话不说，看到最少，就考虑一下DP吧！
②算法结构
A.O(n^2)
首先这道题说“这一组的价值是最大的长乘最大的宽”（长和宽不是小学生的长短区别了，宽可以比长要长。设a[i].x为长，a[i].y为宽）。在一段区间中找最大，最简单的方法是先排序。我们按x的降序为第一关键字，y的降序为第二关键字，排序。
那么我们是否可以得出f[i]=f[j]+a[j+1].x*a[j+1].y呢？（假设1~j自己解决，j+1~i为一组购买）并不可以。因为虽然保证a[j+1].x是后面最大的，但是不保证a[j+1].y最大。
这种情况下，我们扫一遍整个串。如果这个土地和之前的是包含关系，那么这块土地可以不用考虑。（为什么？你还好意思问我为什么？如果这个需要考虑，那么就是把它作为最大的，但如果把它作为一组中最大的，那么还不如把它归到包含它的那一组，让它的下一个变成最大的，明显更优秀）我们用b数组存储筛掉包含关系之后的所有土地。
那么这时候就有一个特殊的性质：b数组中，x是递减的，y是递增的。
我们就能够得出关系式了：
f[i]=mymin(f[i],f[j]+b[j+1].x*b[i].y);
完整代码：
/* O(n^2)代码 不能直接提交 */ #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; struct qq{ long long x,y; }a[51000],b[51000]; long long f[51000]; bool cmp(qq x,qq y) { if(x.x==y.x)return x.y>y.y; else return x.x>y.x; } long long mymin(long long x,long long y) { return x<y?x:y; } int main() { freopen("acquire.in","r",stdin);freopen("acquire.out","w",stdout); memset(f,127,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n ;i++) { scanf("%I64d %I64d",&a[i].x,&a[i].y); } sort(a+1,a+n+1,cmp); int len=0; for(int i=1;i<=n;i++) { if(len==0 || a[i].y>b[len].y) { len++; b[len].x=a[i].x; b[len].y=a[i].y; } } //x递减，y递增 n=len; f[1]=b[1].x*b[1].y; for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { f[i]=mymin(f[i],f[j]+b[j+1].x*b[i].y); } } printf("%I64d",f[n]); return 0; } 此贴终结。
B.O(nlogn)（吧）
这个代码提交上去又超时了（又？）。所以我们要用比DP还优秀的斜率优化。
首先证决策的单调性（自己证吧）
然后推导斜率方程（(ﾉ*･ω･)ﾉ）
设j1<j2<i
则如果j1推出来的结果不优于j2,也就是
f[j1]+b[j1+1].x*b[i].y > f[j2]+b[j2+1].x*b[i].y
将左边只剩下f数组
f[j1]-f[j2] > b[j2+1]*b[i].y - b[j1+1].b[i].y
右边提取公因式，同时两边除以(b[j2+1].x-b[j1+1].x)
关键的一步来了：因为b数组中的x是递减的，所以j2在j1后面，x值较小，所以相减的值是负数。除后不等号方向要变
(f[j1]-f[j2])/(b[j2+1].x-b[j1+1].x) < b[i].y
得到了形如(y1-y2)/(x1-x2)的斜率式子
完整代码
成天就知道看代码
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct qq{ long long x,y; }a[51000],b[51000]; long long f[51000]; int q[51000]; int n; bool cmp(qq x,qq y) { if(x.x==y.x)return x.y>y.y; else return x.x>y.x; } long long Y(int x) { return f[x]; } long long X(int x) { return b[x].x; } double xielv(int x,int y) { return (Y(x)-Y(y))*1.0/(X(y+1)-X(x+1)); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld %lld",&a[i].x,&a[i].y); } sort(a+1,a+n+1,cmp); int len=0; for(int i=1;i<=n;i++) { if(len==0 || a[i].y>b[len].y) { len++; b[len].x=a[i].x; b[len].y=a[i].y; } } int st,ed; st=ed=1; q[1]=0; n=len; for(int i=1;i<=n;i++) { // while(l<r && f[q[st]]-f[q[st+1]] > (b[q[st+1]+1].x-b[q[st]+1].x) * b[i].y)st++; while(st<ed && xielv(q[st],q[st+1])< b[i].y)st++; int j=q[st]; f[i]=f[j]+b[j+1].x*b[i].y; while(st<ed && xielv(q[ed],i) < xielv(q[ed-1],q[ed]))ed--; q[++ed]=i; } printf("%lld",f[len]); return 0; }
