首页 > 代码库 > 【动态规划】【斜率优化】CDOJ1689 分序列
【动态规划】【斜率优化】CDOJ1689 分序列
斜率优化裸题,模型可以看http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html
#include<cstdio> #include<deque> using namespace std; #define EPS 1e-8 typedef long long ll; deque<int>q; int n; ll m,sum[500010],f[500010]; //借鉴了:http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html ll getDP(int i,int j){ return f[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]); } ll getUP(int j,int k){//yj-yk,即斜率的分子部分 return (f[j]+sum[j]*sum[j])-(f[k]+sum[k]*sum[k]); } ll getDOWN(int j,int k){//xj-xk,即斜率的分母部分 return 2ll*(sum[j]-sum[k]); } int main(){ freopen("k.in","r",stdin); while(scanf("%d%lld",&n,&m)!=EOF){ for(int i=1;i<=n;++i){ scanf("%lld",&sum[i]); } for(int i=2;i<=n;++i){ sum[i]+=sum[i-1]; } q.clear(); q.push_back(0); for(int i=1;i<=n;++i){ while(q.size()>1 && getUP(q[1],q[0])<=sum[i]*getDOWN(q[1],q[0])){ q.pop_front(); } f[i]=getDP(i,q.front()); while(q.size()>1 && getUP(i,q.back())*getDOWN(q.back(),q[q.size()-2])<=getUP(q.back(),q[q.size()-2])*getDOWN(i,q.back())){ q.pop_back(); } q.push_back(i); } printf("%lld\n",f[n]); } return 0; }
【动态规划】【斜率优化】CDOJ1689 分序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。