关键词：
裸的斜率优化。。我考场上SB写暴力
#include<algorithm>
#include<iostream>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<ctime>
#include<set>
#include<map>
#define N 3333
#define inf 1e9
using namespace std;
long long sum[N],a[N],b[N],*f=a,*g=b;
int q[N],n,m;
double slop(int x,int y)
return double(g[x]-g[y]+sum[x]*sum[x]-sum[y]*sum[y])/(sum[x]-sum[y]);
int main()
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&sum[i]),sum[i]+=sum[i-1];
for(int i=1;i<=n;i++) f[i]=sum[i]*sum[i];
for(int o=1;o<m;o++)
int l=1,r=1; swap(f,g);q[1]=0;
for(int i=1;i<=n;i++)
while(l<r&&slop(q[l],q[l+1])<2*sum[i])l++;
f[i]=g[q[l]]+(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]]);
while(l<r&&slop(q[r],q[r-1])>slop(q[r],i))r--;
q[++r]=i;
cout<<m*f[n]-sum[n]*sum[n];
bzoj4518[sdoi2016]征途斜率优化
【BZOJ4518】[Sdoi2016]征途DescriptionPine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天... 查看详情
bzoj4518:[sdoi2016]征途(dp+斜率优化)(代码片段)
TimeLimit: 10Sec MemoryLimit: 256MBSubmit: 1875 Solved: 1045[Submit][Status][Discuss]DescriptionPine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。 查看详情
bzoj4518[sdoi2016]征途(斜率优化dp)(代码片段)
我犯了sb错误然后调了1个小时......队列写错了斜率k递增，b取最小值，队列维护凸包即可f[0]的预处理好像有些奇怪？？？我把inf调大就过了？？？1#include<cstdio>2#include<algorithm>3#include<cstring>4#defineilinline5#definelllonglong6... 查看详情
bzoj4518[sdoi2016]征途斜率优化dp
...logs.com/GXZlegend/p/6812435.html题目描述Pine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一... 查看详情
●bzoj4518[sdoi2016]征途
题链：http://www.lydsy.com/JudgeOnline/problem.php?id=4518题解：斜率优化DP首先看看最后答案的形式：设a[i]为第i天走的距离，那么$ANS=frac{sum_{i=1}^{M}(a[i]-overline{x})^2}{M} imes{M^2}$$;qquad=frac{(sum_{i=1}^{M}a[i]^2)-2overl 查看详情
bzoj4518:[sdoi2016]征途（dp+决策单调性分治优化）
题目要求... 化简得... 显然m和sum^2是已知的，那么只要让sigma(si^2)最小，那就变成了求最小平方和的最小值，经典的决策单调性，用分治优化即可。 斜率优化忘得差不多就不写了#include<iostream>#include<cstr... 查看详情
bzoj4518:[sdoi2016]征途
n<=3000个数划分成m段，每段的权值为这一段数字的和，求段的最小方差乘上m平方。所以就是求上边那组平方和的最小值，这个可以dp，f(i,j)表示分成i段，前j个数最小方差，pre表示前缀和，这个式子可以用斜率优化或决策单调... 查看详情
bzoj4518:[sdoi2016]征途
第一眼看到这题的想法：这不就是一题傻逼DP吗。。。水经验然而……诶诶诶DP怎么写%了题解（还被嘲讽%题解比自己AC还多）原来是式子化简错了（囧orz，所以我不化简给你），菜啊。然后写个斜率优化就行（懒得滚）。... 查看详情
[luogu4072][bzoj4518][sdoi2016]征途(代码片段)
题目分析Pine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。Pine希望每一天... 查看详情
bzoj4518:[sdoi2016]征途
【传送门：BZOJ4518】简要题意： 给出n个数，将n个数分成m段，求出这m段数字和的最小方差，然后将方差*m^2题解： DP 我们设ans为最后的答案，sum表示所有的数之和，c[i]表示最优解中第i段数字和 下面式子中，1<=i... 查看详情
bzoj4518：[sdoi2016]征途——题解(代码片段)
...18https://www.luogu.org/problemnew/show/P4072Pine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一... 查看详情
bzoj4518[sdoi2016]征途（分治dp）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4518 【题目大意】 给出一个数列，分成m段，求方差最小，答案乘上m的平方。 【题解】 化简式子可以发现，就是求将数列分成m段，最小化和的平方和。... 查看详情
bzoj4518/luogu4072征途（斜率优化dp）(代码片段)
首先推一波公式： 设f[t][i]为第t天以i为结尾，这时已经算了的最小公差$*m^2$ 设s[i]为1到i的和$$f[t][i]=minf[t-1][j]+m*(s[i]-s[j]-fracs[n]m)^2$$$$f[t][i]=minf[t-1][j]+frac(s[n])^2m-2s[n](s[i]-s[j])+m(s[i]-s[j])^2$$因为一共 查看详情
[bzoj4518]征途
4518:[Sdoi2016]征途TimeLimit: 10Sec MemoryLimit: 256MBDescriptionPine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站... 查看详情
luogup4072[sdoi2016]征途(代码片段)
[SDOI2016]征途大体大概就是推推公式，发现很傻逼的(n^3)DPget60进一步我们发现状态不能入手，考虑优化转移套个斜率优化板子每一层转移来一次斜率优化思路先便便式子[s^2=m^2*fracsum_1^m(a_i-overlinea)^2m][=m*sum_1^m(a_i-overlinea)^2][=m*sum_1^m(... 查看详情
笔记篇斜率优化dpsdoi2016征途
=======传=送=门=======搜题目名会搜出很多奇怪的东西...这个题目似乎有点毒?比如在bzoj和loj上可以1A的代码上会在luoguTLE2个点,在cogsTLE10个点但是根据已有的资料来看数据都是一样的...毒瘤评测姬毁我OI!!!这个题的状态转移方程并不... 查看详情
[sdoi2016]征途(代码片段)
这道题特别坑状态转移是 f[i][k+1]=f[j][k]+(sum[i]-sum[j])*(sum[i]-sum[j]);转换后变为 f[j][k]+sum[j]*sum[j]=f[i][k+1]+2*sum[i]*sum[j];但是我在这里要说的是一个初值的问题通常情况下斜率优化的题目都是不需要赋初值的但因为f[i][1]全都... 查看详情
bzoj4513~4518sdoi2016r1题解
4513:[Sdoi2016]储能表数位dp，f[i][2][2][2]表示前i位，是否卡n的上界，是否卡m的上界，是否卡k的下界，枚举每一维的下一位直接转移。#include<cstdio>#include<cstring>typedefunsignedu32;typedeflonglongll;llx,y,z;intp,q;u32f[61][2][2][2][2];in 查看详情