[洛谷 2900][USACO08MAR]Land Acquisition

题目链接

https://www.luogu.org/problem/P2900

题解

对于两块土地 \(i,j\)，如果 \(w_i<w_j\) 且 \(h_i<h_j\)，那么将这两块土地一块购买，\(i\) 土地对于答案就不会产生任何贡献。

因此我们将所有土地按长度为第一关键字，宽度为第二关键字降序排序，同时排除那些对答案没有贡献的土地。

现在容易发现所有土地的长是递减，宽是递增的。这种情况下，显然将连续一段的土地一起购买比将多个不连续的段一块购买更优。

设 \(f(i)\) 表示前 \(i\) 块土地的最低花费。

容易得到如下状态转移方程：

$$f(i)=\min_{j=1}^{i-1} \{f_j+w_i \times h_{j+1}\}$$

时间复杂度是 \(O(n^2)\) 的，需要优化。

考虑上斜率优化。

假如存在两个决策点 \(a,b\)，且 \(a<b\)。当以 \(a\) 处的决策为更优决策时：

$$f_a+w_i \times h_{a+1} < f_b + w_i \times h_{b+1}$$

$$\frac{f_a-f_b}{h_{b+1}-h_{a+1}} < w_i$$

用单调队列维护即可。时间复杂度 \(O(n)\)。

#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
 long long x,y;
}a[50005];
long long f[50005];
int q[50005];
bool cmp(const node&a,const node&b)
{
 return a.x>b.x||(a.x==b.x&&a.y>b.y);
}
double slope(int x,int y)
{
 return double(f[x]-f[y])/(a[y+1].x-a[x+1].x);
}
int main()
{
 int n,cnt=0;
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>a[i].x>>a[i].y;
 sort(a+1,a+n+1,cmp);
 for(int i=1;i<=n;i++)
  if(a[cnt].y<a[i].y)a[++cnt]=a[i];
 int l=0,r=0;
 for(int i=1;i<=cnt;i++)
 {
  while(l<r&&slope(q[l],q[l+1])<=a[i].y)
   l++;
  f[i]=f[q[l]]+a[q[l]+1].x*a[i].y;
  while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i))
   r--;
  q[++r]=i;
 }
 cout<<f[cnt]<<endl;
 return 0;
}