随着YYHS的OI集训队人数急剧增加，原有的小机房已经容纳不了数量庞大的队员。
于是史老师决定租用一些实验室机位供队员们训练,他正在考虑为N
(1 <= N <= 50,000)位队员租用机位。实验室管理员根据要求给出了N个机位的长和宽，每个机位的长宽满足(1 <= 宽 <=
1,000,000; 1 <= 长 <= 1,000,000).
而机位的租用价格是它的面积，实验室管理员也提出，可以同时租用多个机位.
租用这一组机位的价格是它们最大的长乘以它们最大的宽, 但是机位的长宽不能交换.
如果想租下一个3x5的机位和一个5x3的机位,则他需要付5x5=25.
于是问题出现了，史老师希望租下所有的机位,但是他发现分组来租这些机位可以节省经费.
他需要你帮助他找到最小的经费.
*
第1行: 一个数: N
*
第2..N+1行: 每行包含两个数,分别为机位的长和宽
* 第一行: 最小的可行费用.
4 100 1 15 15 20 5 1 100
500
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; #define maxn 50005 long long f[maxn]; struct note{ ll x,y; friend bool operator <(note a,note b) { return(a.x==b.x&&a.y<b.y||a.x<b.x); } }a[maxn],b[maxn]; ll n,cnt,Q[maxn]; /*f[i]=min（f[j]+b[j+1].y*b[i].x) f[j]+b[j+1].y*b[i].x<f[k]+b[k+1].y*b[i].x f[j]-f[k]/(b[k+1].y-b[j+1].y)>b[i].x -->j is better than k because of b[i].x is getting larger g(i,j)>b[i].x mean i is better than j g(i,j)>g(j,k) :when g(i,j)>b[i].x i is better than j;else k is better than j ;so it‘s fobitted */ double Slope(ll j,ll k) { return (double)(f[j]-f[k])/(b[k+1].y-b[j+1].y); } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) { scanf("%lld %lld",&a[i].x,&a[i].y); } sort(a+1,a+1+n); for(ll i=1;i<=n;i++) { while(cnt&&a[i].y>=b[cnt].y) cnt--; b[++cnt]=a[i]; } ll head,tail; head=tail=1; Q[1]=0; for(ll i=1;i<=cnt;i++) { while(head<tail&&Slope(Q[head],Q[head+1])<=b[i].x) head++; ll front=Q[head]; f[i]=f[front]+b[i].x*b[front+1].y; while(head<tail&&Slope(Q[tail-1],Q[tail])>=Slope(Q[tail],i))tail--; Q[++tail]=i; } cout<<f[cnt]<<endl; }
原文：http://www.cnblogs.com/dancer16/p/7533316.html