首页 > 代码库 > BZOJ 3156 防御准备
BZOJ 3156 防御准备
也是斜率优化。。。。推下式子就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000050 using namespace std; long long n,a[maxn],g[maxn],q[maxn],l,r,f[maxn]; long long read() { char ch;long long data=http://www.mamicode.com/0; while (ch<‘0‘ || ch>‘9‘) ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) { data=data*10+ch-‘0‘; ch=getchar(); } return data; } double k(long long x,long long y) { return (double)(g[x]-g[y])/(x-y); } void dp() { f[1]=a[1];l=r=1;q[l]=1;g[1]=a[1]; for (long long i=2;i<=n;i++) { while ((r-l) && (k(q[l],q[l+1])<=i)) l++; g[i]=f[i-1]+a[i]+i*(i-1)/2; while ((r-l) && (k(q[r-1],q[r])>k(q[r],i))) r--; q[++r]=i; f[i]=f[q[l]-1]+a[q[l]]+(i-q[l])*(i-q[l]+1)/2; } } int main() { n=read(); for (long long i=n;i>=1;i--) a[i]=read(); dp(); printf("%lld\n",f[n]); return 0; }
BZOJ 3156 防御准备
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。