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
FJ分3組買這些土地:
第一組:100x1,
第二組1x100,
第三組20x5 和 15x15 plot.
每組的價格分別為100,100,300, 總共500.

HINT

?

思路 ：這個題目是一個斜率優化的dp，我們先把初始的土地預處理一下，讓土地的h遞增，w遞減，其他一些土地長寬都比某些土地小，這些土地是不會影響答案的。

然后我們設f[i]表示前i個土地的最小費用。

易證，f[i]=min(f[j]+h[i]*w[j+1]); 為了計算方便，將w數組錯一位，f[i]=min(f[j]+h[i]*w[j]); 考慮兩個轉移f[j],f[k]，且k<j<i ; 若對于f[i]從f[j]轉移比從f[k]轉移更優，那么f[j]+h[i]*w[j]<f[k]+h[i]*w[k]; ?

根據線性規劃的知識和斜率的知識，我們維護一個斜率不斷減小的凸包，答案一定在凸包的點上。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i<=b;i++) 5 #define Rep(i,a,b) for(R i=a;i>=b;i--) 6 #define ms(i,a) memset(a,i,sizeof(a)) 7 #define gc() getchar() 8 #define LL long long 9 template<class T>void read(T &x){ 10 x=0; char c=0; 11 while (!isdigit(c)) c=gc(); 12 while (isdigit(c)) x=x*10+(c^48),c=gc(); 13 } 14 int const N=50000+3; 15 int q[N],n,st[N],top,m; 16 LL dp[N],h[N],w[N]; 17 struct node{ 18 int h,w; 19 bool operator < (const node &rhs) const{ 20 if(h!=rhs.h) return h<rhs.h; 21 return w>rhs.w; 22 } 23 }a[N]; 24 int main(){ 25 read(n); 26 rep(i,1,n) read(a[i].h),read(a[i].w); 27 sort(a+1,a+n+1); 28 st[top=1]=1; 29 rep(i,2,n)if(a[i].h!=a[i-1].h){ 30 while (top && a[i].w>=a[st[top]].w) top--; 31 st[++top]=i; 32 } 33 m=top; 34 w[0]=a[st[1]].w; 35 rep(i,1,m) h[i]=a[st[i]].h,w[i]=a[st[i+1]].w; 36 int st=0,ed=0; 37 rep(i,1,m){ 38 while (st<ed && dp[q[st+1]]-dp[q[st]]<h[i]*(w[q[st]]-w[q[st+1]])) st++; 39 dp[i]=dp[q[st]]+h[i]*w[q[st]]; 40 while (st<ed && (dp[i]-dp[q[ed]])*(w[q[ed]]-w[q[ed-1]])>(dp[q[ed]]-dp[q[ed-1]])*(w[i]-w[q[ed]])) ed--; 41 q[++ed]=i; 42 } 43 cout<<dp[m]<<endl; 44 return 0; 45 } View Code

?

轉載于:https://www.cnblogs.com/ZJXXCN/p/10212121.html

總結

以上是生活随笔為你收集整理的bzoj 1597 土地购买的全部內容，希望文章能夠幫你解決所遇到的問題。

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