洛谷2900 [USACO08MAR]土地征用Land Acquisition （斜率优化+dp）

自闭的一批....为什么斜率优化能这么自闭。

首先看到这个题的第一想法一定是按照一个维度进行排序。

那我们不妨直接按照\(h_i\)排序。

我们令\(dp[i]\)表示到了第\(i\)个矩形的答案是多少。

之后我们会发现，对于\(dp[i]\)的转移

\[dp[i]=dp[j-1]+h[j]*mn[j][i]
\]

其中\(mn[j][i]\)表示\(j到i\)的最小值。

qwq我们发现对于一个含有最值的柿子，他没法转移qwq

那我们不妨仔细考虑一下。

对于一个排在\(i\)后面的矩阵\(j\)，如果他的\(w\)小于前缀\(w_{max}\)，那么他就可以直接和之前某个矩阵合买了。

那这样就能去掉很多没有用的矩阵

剩下的矩阵就是一个\(h\)单调不升，\(w\)单调不降的序列。

那么这时候

\(dp[i]=max(dp[j-1]+h[j]*w[i])\)

经过推柿子

\[\frac{dp[j-1]-dp[k-1]}{h[j]-h[k]} > -w[i]
\]

然后直接斜率优化就可以qwq

这里有两个要注意的地方！！！！！！

首先，我们要比较的是当前的\(w\)和前缀\(w\)的最大值，而不能比较他的和上一个矩阵（因为上一个矩阵可能也是被完全替代的）。

其次！因为\(h[j]-h[k]<0\) 所以移项要改变！符号！

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk make_pair

#define ll long long

#define int long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2e5+1e2;

struct Node{

	int h,w;

};

Node a[maxn];

int dp[maxn];

int n;

struct Point{

	int x,y;

};

Point q[maxn];

int chacheng(Point x,Point y)

{

	return x.x*y.y-x.y*y.x;

}

bool count(Point i,Point j,Point k)

{

   Point x,y;

   x.x=k.x-i.x;

   x.y=k.y-i.y;

   y.x=k.x-j.x;

   y.y=k.y-j.y;

   if (chacheng(x,y)>=0) return true;

   return false;

}

int head=1,tail=0;

void push(Point x)

{

	while(tail>=head+1 && count(q[tail-1],q[tail],x)) tail--;

	q[++tail]=x;

}

void pop(int lim)

{

	while (tail>=head+1 && q[head+1].y-q[head].y<lim*(q[head+1].x-q[head].x)) head++;

}

bool cmp(Node a,Node b)

{

	if(a.h==b.h) return a.w>b.w;

	return a.h>b.h;

}

signed main()

{

  n=read();

  for (int i=1;i<=n;i++) a[i].w=read(),a[i].h=read();

  sort(a+1,a+1+n,cmp);

  push((Point){a[1].h,0});

  dp[1]=a[1].w*a[1].h;

  int mx = a[1].w;

  for (int i=2;i<=n;i++)

  {

  	if (a[i].w<=mx)

  	{

  		dp[i]=dp[i-1];

  		continue;

	}

	mx=max(mx,a[i].w);

	dp[i]=dp[i-1]+a[i].w*a[i].h;

  	pop((-1ll)*a[i].w);

  	Point now = q[head];

  	dp[i]=min(now.y+a[i].w*now.x,dp[i]);

  	push((Point){a[i].h,dp[i-1]});

  }

  cout<<dp[n];

  return 0;

}

巴特西

洛谷2900 [USACO08MAR]土地征用Land Acquisition （斜率优化+dp）

最新文章

热门文章