既然每塊都要買, 那么一塊土地被另一塊包含就可以不考慮. 先按長排序, 去掉不考慮的土地, 剩下的土地長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

?

轉載于:https://www.cnblogs.com/JSZX11556/p/4781723.html

總結

以上是生活随笔為你收集整理的BZOJ 1597: [Usaco2008 Mar]土地购买( dp + 斜率优化 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。