bzoj4518 [ SDOI2016 ] --斜率优化DP
2018-06-17 23:39:13来源:未知 阅读 ()
设x[i]为第i天走的路程,s为路程总和,则:
ans=[(s/m-x[1])^2+(s/m-x[2])^2+(s/m-x[3])^2+...+(s/m-x[m])^2]*m
=[(s-x[1]*m)^2+(s-x[2]*m)^2+(s-x[3]*m)^2]+...+(s-x[m]*m)^2)]/m
=s^2+m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-2*(x[1]+x[2]+x[3]+...+x[m])*s
=m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-s^2
由于m,s不变,问题可以转化为将一个长为n的序列划分成m段,求最小平方和。
令f[i][j]为将长为j的序列划分成i段的最小平方和,则
f[i][j]=min(f[i][k]+(sum[j]-sum[k])^2),0<k<j
很明显的斜率优化。
斜率优化过程如下:
设p<k<j,在求f[i][j]时k比p优,于是可得如下方程:
f[i-1][k]+(sum[j]-sum[k])^2<f[i-1][p]+(sum[j]-sum[p])^2
f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2)<2*(sum[k]-sum[p])*sum[j]
(f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2))/(2*sum[k]-2*sum[p])<sum[j]
如果令y[i-1][t]=f[i-1][t]+sum[t]^2,x[i-1][t]=2*sum[t],
则原式可化为:(y[i-1][k]-y[i-1][p])/(x[i-1][k]-x[i-1][p])<sum[j],不就是线段kp的斜率小于sum[j]吗?
令g[i][j](i>j)为线段ij的斜率。
于是在求f[i]时维护一个序列,满足对任意j(j>2),g[j][j-1]>g[j-1][j-2],则f[i][j]的最优值就从序列中斜率小于sum[j]的序号最大的线段的右端点转移。
时间复杂度从O(n*n*m)降到O(n*m)
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define ll long long ll i,j,k,n,m,f[3001][3001],x[3001],y[3001][3001],sum[3001],s,l,r,q[3001]; int main() { scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%lld",&sum[i]),s+=sum[i],sum[i]+=sum[i-1],x[i]=sum[i]<<1,f[1][i]=sum[i]*sum[i],y[1][i]=f[1][i]<<1; for(i=2;i<=m;i++){ l=r=0; for(j=1;j<=n;j++){ while(l<r&&y[i-1][q[l+1]]-y[i-1][q[l]]<=sum[j]*(x[q[l+1]]-x[q[l]]))l++; f[i][j]=f[i-1][q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]); y[i][j]=f[i][j]+sum[j]*sum[j]; while(l<r&&(x[q[r]]-x[q[r-1]])*(y[i-1][j]-y[i-1][q[r-1]])<=(x[j]-x[q[r-1]])*(y[i-1][q[r]]-y[i-1][q[r-1]]))r--; q[++r]=j; } } printf("%lld\n",f[m][n]*m-s*s); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- 斜率优化dp学习笔记 洛谷P3915[HNOI2008]玩具装箱toy 2019-08-16
- 斜率优化dp—从入门到吐血 2018-12-19
- BZOJ4517: [Sdoi2016]排列计数(组合数+错位排列) 2018-06-27
- bzoj1492 [ NOI2007 ] --斜率优化DP+cdq分治 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash