bzoj3437 小P的牧场

题目

斜率优化第一题。。。

其实熟悉之后，发现其实并没有什么难度，就是数学推公式就好了

朴素dp

for(register LL i=1;i<=n;i++)scanf("%lld",&a[i]); for(register LL i=1;i<=n;i++)scanf("%lld",&b[i]); for(register LL i=1;i<=n;i++)A[i]=A[i-1]+b[i]; for(register LL i=1;i<=n;i++)B[i]=B[i-1]+b[i]*i; memset(f,63,sizeof(f)); f[1]=a[1]; for(register LL i=2;i<=n;i++) for(register LL j=1;j<i;j++) f[i]=min(f[i],f[j]+i*(A[i]-A[j])-(B[i]-B[j])+a[i]); cout<<f[n];

之后推一推斜率 ((f[i]-f[j])+(B[i]-B[j]))/(double)(A[i]-A[j])

套个模板就好了。

顺便粘个模板吧。。

#include<bits/stdc++.h> #define N 1000000 #define LL long long using namespace std; LL f[N+1],A[N+1],B[N+1]; LL a[N+1],b[N+1]; LL n; LL q[N+1],l,r; double slope(LL i,LL j) { return (double)((f[i]-f[j])+(B[i]-B[j]))/(double)(A[i]-A[j]); } int main() { scanf("%lld",&n); for(register LL i=1;i<=n;i++)scanf("%lld",&a[i]); for(register LL i=1;i<=n;i++)scanf("%lld",&b[i]); for(register LL i=1;i<=n;i++)A[i]=A[i-1]+b[i]; for(register LL i=1;i<=n;i++)B[i]=B[i-1]+b[i]*i; /* memset(f,63,sizeof(f)); f[1]=a[1]; for(register LL i=2;i<=n;i++) for(register LL j=1;j<i;j++) f[i]=min(f[i],f[j]+i*(A[i]-A[j])-(B[i]-B[j])+a[i]); cout<<f[n]; */ l=1,r=0,q[++r]=0; for(register LL i=1;i<=n;i++) { while(l<r&&slope(q[l+1],q[l])<=i)l++; LL tmp=q[l]; f[i]=f[tmp]+i*(A[i]-A[tmp])-(B[i]-B[tmp])+a[i]; while(l<r&&slope(i,q[r])<slope(q[r],q[r-1]))r--; q[++r]=i; } cout<<f[n]; return 0; }