「BZOJ3156」防御准备
Description
.jpg)
Input
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
Sample Input
10
2 3 1 5 4 5 6 3 1 2
Sample Output
18
HINT
1<=N<=10^6,1<=Ai<=10^9
题解
裸的斜率优化
把a[i]都反过来
sum[i]=sum[i-1]+i
f[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*j}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> #include<cstdio> #define ll long long using namespace std; int n,l,r; ll ans=(1LL<<60),f[1000005],sum[1000005]; int a[1000005],q[1000005]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline double slop(ll j,ll k) { return (f[j]-f[k]-sum[j]+sum[k]+j-k+j*j-k*k)/(double)(j-k); } int main() { n=read(); for(int i=n;i;i--) a[i]=read(); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+i; f[1]=a[1];q[1]=1;l=r=1; ans=min(ans,f[1]+sum[n]-sum[1]-n+1); for(int i=2;i<=n;i++) { while(l<r&&slop(q[l],q[l+1])<i)l++; int t=q[l]; f[i]=f[t]+sum[i-1]-sum[t]-(ll)(i-t-1)*t+a[i]; ans=min(ans,f[i]+sum[n]-sum[i]-(ll)(n-i)*i); while(l<r&&slop(q[r-1],q[r])>slop(q[r],i))r--; q[++r]=i; } printf("%lld",ans); return 0; } |
Subscribe
计数器 9787812
OI 课件=>
OI 课件=>