【洛谷 P2900】 [USACO08MAR]土地征用Land Acquisition（斜率优化，单调栈）

题目链接

 双倍经验

设\(H\)表示长，\(W\)表示宽。

若\(H_i<H_j\)且\(W_i<W_j\)，显然\(i\)对答案没有贡献。

于是把所有点按\(H\)排序，然后依次加入一个按\(W\)降序排序的单调栈。

这个单调栈里就是一定对答案有贡献的点，现在的问题就是把这些点分段，使总费用最小。

设\(f[i]\)表示前\(i\)块土地的最小费用。

然后枚举断点\(0<=j<i\)，则\(f[i]=\min(f[j]+W_{j+1}*H_i)\)

斜率优化搞一搞就行了。

// f[i] = f[j] + x[i] * y[j + 1]

// f[j] = -x[i] * y[j + 1] - f[i]

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 50010;

#define ll long long

inline ll min(const ll a, const ll b){

	return a < b ? a : b;

}

int n, top;

struct point{

	int x, y;

	int operator < (const point A) const{

		return x != A.x ? x < A.x : y < A.y;

	}

}a[MAXN], st[MAXN];

int q[MAXN], head, tail;

ll f[MAXN];

inline double k(int i, int j){

	return (f[i] - f[j]) / (st[i + 1].y - st[j + 1].y);

}

int main(){

	scanf("%d", &n);

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

	   scanf("%d%d", &a[i].x, &a[i].y);

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

	for(int i = 1; i <= n; ++i){

		while(top && st[top].y <= a[i].y) --top;

		st[++top] = a[i];

	}

	for(int i = 1; i <= top; ++i){

	   while(head < tail && k(q[head], q[head + 1]) > -st[i].x) ++head;

	   int j = q[head];

	   f[i] = f[j] + (ll)st[i].x * st[j + 1].y;

	   while(head < tail && k(q[tail - 1], q[tail]) <= k(q[tail], i)) --tail;

	   q[++tail] = i;

    }

    printf("%lld\n", f[top]);

    return 0;

}

巴特西

【洛谷 P2900】 [USACO08MAR]土地征用Land Acquisition（斜率优化，单调栈）

最新文章

热门文章