首页 > 代码库 > 【bzoj 3156】防御准备
【bzoj 3156】防御准备
Description
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
long long!long long!long long!
又是一发惨剧现场……
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int N=1000050; 6 long long a[N],f[N],n,t,q[N],l=0,r=0; 7 long long read() 8 { 9 long long x=0,f=1;char c=getchar(); 10 while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} 11 while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} 12 return x*f; 13 } 14 double slope(long long k,long long j) 15 {return (2.0*(f[j]-f[k])+j*(j+1)-k*(k+1))/(2.0*(j-k));} 16 int main() 17 { 18 n=read(); 19 for(int i=1;i<=n;i++)a[i]=read(); 20 for(long long i=1;i<=n;i++) 21 { 22 while(l<r&&slope(q[l],q[l+1])<i)l++; 23 t=q[l]; 24 f[i]=f[t]+(long long)(i-t)*(i-t-1)/2+a[i]; 25 while(l<r&&slope(q[r-1],q[r])>slope(q[r],i))r--; 26 q[++r]=i; 27 } 28 printf("%lld",f[n]); 29 return 0; 30 } 31
【bzoj 3156】防御准备
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。