目录
BZOJ1597 土地购买题解ｃｏｄｅ
BZOJ1597 土地购买
题目传送门
题解
还是一道经典的斜率优化\(Dp\)，我们先将土地按长度升序排序，然后在这个排序中找出一个长度\(a\)升序，长度\(b\)降序的序列（因为如果\(b\)在某一处是升序的话，那么前面的一部分土地就没有必要买了）。之后就很容易写出转移方程：
\(dp[i]=min(dp[j]+a[i]*b[j+1])\)
如果\(k>j\)并且\(k\)比\(j\)更优，则\(dp[j]+a[i]*b[j+1]\geq dp[k]+a[i]*b[k+1]\)，整理之后可以得出：
\(a[i]\geq \frac{dp[k]-dp[j]}{b[j+1]-b[k+1]}\)
最后就是套公式了。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=1e5+500;
int n,tot;
struct plot {
ll a,b;
bool operator < (const plot &rhs) const {
return a!=rhs.a?a<rhs.a:b<rhs.b;
}
}p[maxn],pp[maxn];
ll f[maxn];
int l,r;
int que[maxn];
/*==================Define Area================*/
double Cal(int x,int y) {
return (double)(f[y]-f[x])/(double)(pp[x+1].b-pp[y+1].b);
}
int main() {
read(n);
for(int i=1;i<=n;i++) {
read(p[i].a);read(p[i].b);
}
sort(p+1,p+1+n);
for(int i=1;i<=n;i++) {
while(tot&&pp[tot].b<=p[i].b) tot--;
pp[++tot]=p[i];
}
for(int i=1;i<=tot;i++) {
while(l<r&&Cal(que[l],que[l+1])<pp[i].a) l++;
int t=que[l];
f[i]=f[t]+pp[i].a*pp[t+1].b;
while(l<r&Cal(que[r],i)<Cal(que[r-1],que[r])) r--;
que[++r]=i;
}
printf("%lld\n",f[tot]);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9434986.html
相关资源：JAVA上百实例源码以及开源项目
