1597: [Usaco2008 Mar]土地购买
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块土地.
100 1
15 15
20 5
1 100
输入解释:
共有4块土地.
Sample Output
500
HINT
FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和 15x15 plot. 每组的价格分别为100,100,300, 总共500.
算法一：DP+栈优化
复杂度O(n log n)
蒟蒻wy表示刚开始打的比较挫。。。
#include<cstdio>
#include<algorithm>
using namespace std;
#define MaxN 50010
int N,cnt;
struct point{
int x,y;
point(){}
point(int a,int b){
x=a; y=b;
}
}P[MaxN];
int st[MaxN];
int b[MaxN],e[MaxN],t,w;
long long f[MaxN];
bool cmp(point a,point b){
return a.x>b.x || a.x==b.x&&a.y>b.y;
}
int main(){
scanf("%d",&N);
for (int i=1;i<=N;++i){
int x,y;
scanf("%d%d",&x,&y);
P[i]=point(x,y);
}
sort(P+1,P+N+1,cmp);
for (int i=1;i<=N;++i)
if ( i==1 || P[cnt].y<P[i].y )
P[ ++cnt ]=P[i];
b[0]=1;
e[ st[ t=0 ] =0 ]=cnt;
for (int i=1;i<=cnt;++i){
while ( e[ st[w] ] < i ) ++w;
// b[st[w]]=i;
f[i]=f[ st[w] ]+(long long)P[ st[w]+1 ].x*P[i].y;
if ( f[ st[t] ]+(long long)P[ st[t]+1 ].x*P[cnt].y < f[i]+(long long)P[i+1].x*P[cnt].y ) continue;
while ( w<=t && f[ st[t] ]+(long long)P[ st[t]+1 ].x*P[ b[ st[t] ] ].y >= f[i]+(long long)P[i+1].x*P[ b[ st[t] ] ].y ) --t;
int be=e[ st[t] ]+1,l=b[ st[t] ],r=e[ st[t] ];
while (l<=r){
int mid=(l+r)/2;
if (f[ st[t] ]+(long long)P[ st[t]+1 ].x*P[mid].y >= f[i]+(long long)P[i+1].x*P[mid].y){
be=mid; r=mid-1;
}
else l=mid+1;
}
e[ st[t] ]=be-1; st[++t]=i; b[i]=be; e[i]=cnt;
}
printf("%lld\n",f[cnt]);
}
#include<cstdio>
#include<algorithm>
using namespace std;
#define MaxN 50010
int N,cnt;
struct point{
int x,y;
point(){}
point(int a,int b){
x=a; y=b;
}
}P[MaxN];
int st[MaxN];
int b[MaxN],e[MaxN],t,w;
long long f[MaxN];
bool cmp(point a,point b){
return a.x>b.x || a.x==b.x&&a.y>b.y;
}
long long calc(int a,int b){
return f[a]+(long long)P[a+1].x*P[b].y;
}
int main(){
scanf("%d",&N);
for (int i=1;i<=N;++i){
int x,y;
scanf("%d%d",&x,&y);
P[i]=point(x,y);
}
sort(P+1,P+N+1,cmp);
for (int i=1;i<=N;++i)
if ( i==1 || P[cnt].y<P[i].y )
P[ ++cnt ]=P[i];
b[0]=1;
e[ st[ t=0 ] =0 ]=cnt;
for (int i=1;i<=cnt;++i){
while ( e[ st[w] ] < i ) ++w;
b[st[w]]=i;
f[i]=calc(st[w],i);
if ( calc(st[t],cnt) < calc(i,cnt) ) continue;
while ( w<=t && calc(st[t],b[st[t]]) >= calc(i,b[st[t]]) ) --t;
int be=e[ st[t] ]+1,l=b[ st[t] ],r=e[ st[t] ];
while (l<=r){
int mid=(l+r)/2;
if (calc(st[t],mid) >= calc(i,mid)){
be=mid; r=mid-1;
}
else l=mid+1;
}
e[ st[t] ]=be-1; st[++t]=i; b[i]=be; e[i]=cnt;
}
printf("%lld\n",f[cnt]);
}
算法二：DP+斜率优化
复杂度O(n)
wy表示忘记初始化了，然后查了很久。。。QAQ
#include<cstdio>
#include<algorithm>
using namespace std;
#define MaxN 50010
int N,cnt;
typedef long long LL;
struct point{
int x,y;
point(){}
point(int a,int b){
x=a; y=b;
}
}P[MaxN];
int Q[MaxN],ql,qr;
LL f[MaxN],X[MaxN],Y[MaxN];
bool cmp(point a,point b){
return a.x>b.x || a.x==b.x&&a.y>b.y;
}
LL calc(int a,int b){
return f[a]+(LL)P[a+1].x*P[b].y;
}
bool check(int p,int q,int o){
return (X[q]-X[o])*(Y[p]-Y[o])-(X[p]-X[o])*(Y[q]-Y[o])>=0;
}
int main(){
scanf("%d",&N);
for (int i=1;i<=N;++i){
int x,y;
scanf("%d%d",&x,&y);
P[i]=point(x,y);
}
sort(P+1,P+N+1,cmp);
for (int i=1;i<=N;++i)
if ( i==1 || P[cnt].y<P[i].y )
P[ ++cnt ]=P[i];
Q[ ql=qr=1 ]=0;
X[0]=P[1].x; Y[0]=0; //论初始化的重要性
for (int i=1;i<=cnt;++i){
while ( ql<qr && calc(Q[ql],i)>=calc(Q[ql+1],i) ) ++ql;
f[i]=calc(Q[ql],i);
X[i]=P[i+1].x; Y[i]=f[i];
while ( ql<qr && check(Q[qr],Q[qr-1],i) ) --qr;
Q[++qr]=i;
}
printf("%lld\n",f[cnt]);
}
Ps:以上解法详见 1D/1D动态规划优化初步
评论 (0)
