BZOJ 1597: [Usaco2008 Mar]土地购买( dp + 斜率优化 )

既然每块都要买, 那么一块土地被另一块包含就可以不考虑. 先按长排序, 去掉不考虑的土地, 剩下的土地长x递增, 宽y递减

dp(v) = min{ dp(p)+x_v*y_p+1 }

假设dp(v)由i转移比由j转移优(i>j), 那么

dp(i)+x_v*y_i+1 < dp(j)+x_v*y_j+1

化简得 (dp(i) - dp(j))/(y_i+1-y_j+1) > -x_v

然后就斜率优化, 单调队列维护一个下凸函数

-----------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 50009;

struct O {

int x, y;

inline void Read() {

scanf("%d%d", &x, &y);

}

bool operator < (const O &o) const {

return x < o.x || (x == o.x && y < o.y);

}

} A[maxn];

int N = 0, r[maxn], Q[maxn];

ll dp[maxn];

void init() {

int n; scanf("%d", &n);

for(int i = 0; i < n; i++) A[i].Read();

sort(A, A + n);

int mx = 0;

for(int i = n; i--; ) {

if(A[i].y > mx) r[++N] = i;

mx = max(mx, A[i].y);

}

for(int L = 1, R = N; L < R; L++, R--) swap(r[L], r[R]);

}

inline double slope(int a, int b) {

return (double) (dp[b] - dp[a]) / (A[r[b + 1]].y - A[r[a + 1]].y);

}

void work() {

int qh = 0, qt = 0;

dp[Q[qt++] = 0] = 0;

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

while(qt - qh > 1 && slope(Q[qh], Q[qh + 1]) > -A[r[i]].x) qh++;

dp[i] = dp[Q[qh]] + ll(A[r[i]].x) * A[r[Q[qh] + 1]].y;

while(qt - qh > 1 && slope(Q[qt - 2], Q[qt - 1]) < slope(Q[qt - 1], i)) qt--;

Q[qt++] = i;

}

printf("%lld\n", dp[N]);

}

int main() {

init();

work();

return 0;

}

-----------------------------------------------------------------------------

1597: [Usaco2008 Mar]土地购买

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2398  Solved: 869
[Submit][Status][Discuss]

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

Input

* 第1行: 一个数: N

* 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽

Output

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

Sample Input

4
100 1
15 15
20 5
1 100

输入解释:

共有4块土地.

Sample Output

500

HINT

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

Source

Gold