[USACO Mar08]土地购买 斜率优化

发布于 2017-06-14  2.19k 次阅读


[toggle hide="yes" title="题面" color=""]

农夫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块土地.

输出格式:

  • 第一行: 最小的可行费用.

样例输出

输出解释:

FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和 15x15 plot. 每组的价格分别为100,100,300, 总共500.

[/toggle]

观察发现,若矩形A的长宽均大于矩形B,则选中矩形B不需要花费额外费用。

所以先进行二元组排序,维护一个单调栈,保证在x单调增的同时y单调减(类似样例的形式)。

而后,选择的矩形即为连续的区间,所以搞成了一个线性DP。

设f[i]:到i为止组成新块的最小花费,则f[i]=min{f[j]+x[i]*y[j+1]} (0<=j<i)

 

斜率优化:

考虑两个决策j和k,j<k且j更优,则将上式化简可得:(f[j]-f[k])/(y[k+1]-y[j+1])>x[i]。

其中不等号左边的式子即为斜率。即当满足slope(j,k)>x[i]时,j更优,反之k不比j差(考虑等号)。

用单调队列维护可选的转移点。考虑队首的两个点:当slope(q[h],q[h+1])<=x[i]时,q[h+1]肯定更优,可以直接h++。考虑队尾的3个点:当slope(q[t-1],q[t])>slope(q[t],i)时,若slope(q[t],i)>x[i],则q[t]比i优,但是q[t-1]比q[t]更优,此时q[t]不会是最优转移点;当x[i]在中间时,依旧是q[t-1]更优;当x[i]>slope(q[t-1],q[t])时,q[t]比q[t-1]优,但是i比q[t]更优。  综上,当slope(q[t-1],q[t])>slope(q[t],i)时,q[t]肯定不是最优转移点,可以t--。

这样,维护了最优性质,每次计算f[i]即可直接选最优点,时间复杂度O(n)。

上代码:

[toggle hide="yes" title="代码" color=""]

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974