[BZOJ 1911][Apio2010]特别行动队：DP斜率优化

本文主要是介绍[BZOJ 1911][Apio2010]特别行动队：DP斜率优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

DP方程：

f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)

如果j>k且j比k更优，则

f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i]

/*
User:Small
Language:C++
Problem No.:1911
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=1e6+5;
int n,a,b,c,stk[M],tp;
ll sum[M],f[M];
ll sqr(ll x){return x*x;
}
ll slopup(int j,int k){return f[k]-f[j]+a*(sqr(sum[k])-sqr(sum[j]))+b*(sum[j]-sum[k]);
}
ll slopdown(int j,int k){return (sum[k]-sum[j])*a*2;
}
double slop(int j,int k){return (double)slopup(j,k)/(double)slopdown(j,k);
}
ll cal(int i,int j){return f[j]+a*sqr(sum[i]-sum[j])+b*(sum[i]-sum[j])+c;
}
int main(){freopen("data.in","r",stdin);//scanf("%d%d%d%d",&n,&a,&b,&c);for(int i=1;i<=n;i++) scanf("%lld",&sum[i]);for(int i=1;i<=n;i++) sum[i]+=sum[i-1];for(int i=1,j=0;i<=n;i++){while(j<tp&&slop(stk[j],stk[j+1])<sum[i]) j++;f[i]=cal(i,stk[j]);while(j<tp&&slop(stk[tp-1],stk[tp])>slop(stk[tp],i)) tp--;stk[++tp]=i;}printf("%lld",f[n]);return 0;
}

这篇关于[BZOJ 1911][Apio2010]特别行动队：DP斜率优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---