【BZOJ4518】[Sdoi2016]征途 斜率优化
优化 斜率
2023-09-11 14:15:27 时间
【BZOJ4518】[Sdoi2016]征途
Description
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v,可以证明,v×m^2是一个整数。为了避免精度误差,输出结果时输出v×m^2。
Input
第一行两个数 n、m。
第二行 n 个数,表示 n 段路的长度
Output
一个数,最小方差乘以 m^2 后的值
Sample Input
5 2
1 2 5 8 6
1 2 5 8 6
Sample Output
36
HINT
1≤n≤3000,保证从 S 到 T 的总路程不超过 30000
题解:我承认自己写丑了~又一次体会到了二维斜率优化的巨大宽度的恐惧~
想看详细的DP推导过程和一维的斜率优化请见神犇的博客
#include <cstdio> #include <iostream> #include <cstring> using namespace std; typedef long long ll; int n,m; int q[4010][3010],h[3010],t[3010]; ll f[30010][3010],v[3010],s[3010]; ll p; ll y(int i,int j) { return f[i][j]+s[i]*s[i]+2*p*s[i]; } int main() { scanf("%d%d",&n,&m); int i,j; for(i=1;i<=n;i++) scanf("%lld",&v[i]),s[i]=s[i-1]+v[i]*m; p=s[n]/(ll)m; for(i=1;i<=m;i++) h[i]=1,t[i]=0,q[1][i]=0; h[0]=t[0]=1,q[1][0]=0; memset(f,0x3f,sizeof(f)); f[0][0]=0; for(i=1;i<=n;i++) { for(j=min(i,m);j>=1;j--) { while(h[j-1]<t[j-1]&& y(q[h[j-1]+1][j-1],j-1)-y(q[h[j-1]][j-1],j-1)<= 2*s[i]*(s[q[h[j-1]+1][j-1]]-s[q[h[j-1]][j-1]])) h[j-1]++; f[i][j]=f[q[h[j-1]][j-1]][j-1]+(s[i]-s[q[h[j-1]][j-1]]-p)*(s[i]-s[q[h[j-1]][j-1]]-p); while(h[j]<t[j]&& (y(q[t[j]][j],j)-y(q[t[j]-1][j],j))*(s[i]-s[q[t[j]][j]])>= (y(i,j)-y(q[t[j]][j],j))*(s[q[t[j]][j]]-s[q[t[j]-1][j]])) t[j]--; q[++t[j]][j]=i; } } printf("%lld",f[n][m]/m); return 0; }
相关文章
- [转] webpack之前端性能优化(史上最全,不断更新中。。。)
- 相约八点,UWA六月直播第三弹-Unity中动画系统的性能优化方案
- 【BZOJ4311】向量(线段树分治,斜率优化)
- 【BZOJ3437】小P的牧场(动态规划,斜率优化)
- 【BZOJ2684】【CEOI2004】锯木厂选址(斜率优化,动态规划)
- 【BZOJ1096】【ZJOI2007】仓库建设(斜率优化,动态规划)
- 【Luogu2900】土地征用(斜率优化,动态规划)
- 【BZOJ1911】【APIO2010】特别行动队(斜率优化,动态规划)
- 【BZOJ1010】【HNOI2008】玩具装箱(斜率优化,动态规划)
- 【BZOJ2726】[SDOI2012]任务安排 斜率优化+cdq分治
- 【BZOJ3218】a + b Problem 可持久化线段树优化建图
- 【BZOJ3437】小P的牧场 斜率优化
- 一条经典SQL语句优化实例
- HDU 2829 Lawrence (斜率优化DP或四边形不等式优化DP)
- Android性能优化之使用线程池处理异步任务
- 转 zabbix 优化方法 以及 后台数据库查询方法 两则
- 《深入解析sas:数据处理、分析优化与商业应用》一第3章 对单个数据集的处理
- SQLServer性能优化专题
- Python代码运行不够流畅?看大神如何多角度优化!
- Elasticsearch 企业级别性能优化(一)
- 陕西省以大数据助力产业结构优化转型升级
- Kylin 学习笔记(二)-----Kylin增量构建入门、Cube碎片管理、JDBC连接、Cube简单优化
- 【bzoj4709】[Jsoi2011]柠檬 斜率优化
- 【bzoj4518】[Sdoi2016]征途 斜率优化dp