BZOJ 3437 小P的牧場斜率優化

2019-11-08 19:47:18

字體：大中小

來源：轉載

供稿：網友

#include <cstdio>#include <cstring>#include <algorithm>#include <cstring>#include <cmath>#define MAXN 1000005#define N 100#define LL long long#define INF 1000000005#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;const double eps = 1e-8;/* http://www.lydsy.com/JudgeOnline/PRoblem.php?id=3437 Pi為每個牧場放牧數量 Ci為在i點建立控制點的花費 Si為P的前綴和 Bi為i*Pi的前綴和考慮假如i+1到j的牧場都在0號位置時花費為(Si-Sj)*i; 但它們不在0號位置所以每個物品可以少花費Pi*i 因此在i和j建立控制點的代價為 (Si-Sj)*i-(Bi-Bj) Fi=min{Fj+(Si-Sj)*i-(Bi-Bj)}+Ci Sj*i+Fi+Bi-Si*i=Fj+Bj k=i,b=Fi+Bi-Si*i-Ci x=Sj,y=Fj+Bj 斜率優化即可*/LL read(){ LL t=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f;}LL n,l=1,r=0;LL f[MAXN],q[MAXN],b[MAXN],c[MAXN],p[MAXN],x[MAXN],s[MAXN];double getk(int i,int j){ return (double)(f[i]+b[i]-f[j]-b[j])/(double)(s[i]-s[j]);}int main(){ n=read(); for(int i=1;i<=n;i++) c[i]=read(); for(int i=1;i<=n;i++) p[i]=read(); for(int i=1;i<=n;i++) s[i]=s[i-1]+p[i],b[i]=b[i-1]+i*p[i]; q[++r]=0; for(int i=1;i<=n;i++) { while(l<r&&getk(q[l],q[l+1])<i) l++; int j=q[l]; f[i]=f[j]+(s[i]-s[j])*i-(b[i]-b[j])+c[i]; while(l<r&&getk(i,q[r])<getk(q[r],q[r-1])) r--; q[++r]=i; } printf("%lld",f[n]); return 0;}

上一篇：sql執行順序以及on和where的區別

下一篇：NOI 2007 貨幣兌換 cash CDQ分治