「SDOI2016」征途

先浅浅复制一个方差

显然dp，可以搞一个

$dp[i][j]$为前i段路程j天到达的最小方差

开始暴力转移

$dp[i][j]=min(dp[k][j-1]+?)(j-1\leq k\leq i-1)$这咋写？还是需要转换一下

开始了，but题目的方差还需要m^2,很好

以下x为m天行走的平均值，s[i]为1~i段路的总路程

那么x可以算对吧:$x=\frac{s[n]}{m}$

\[m\times \sum^m_{i=1}(x_i-x)^2\\
=m\times \sum^m_{i=1}(x_i^2+x^2-2xx_i)\\
=m\times (\sum^m_{i=1}x_i^2+\sum^m_{i=1}x^2-\sum^m_{i=1}2xx_i)\\
=m\times (\sum^m_{i=1}x_i^2+\frac{s[n]^2}{m}-\frac{2s[n]}{m}\sum^m_{i=1}x_i)\\
=m\times (\sum^m_{i=1}x_i^2+\frac{s[n]^2}{m}-\frac{2s[n]^2}{m})\\
=m\times (\sum^m_{i=1}x_i^2-\frac{s[n]^2}{m})\\
=m\times \sum^m_{i=1}x_i^2-s[n]^2
\]

是不是感觉快完了推真爽

所以我们似乎只需要维护$\sum^m_{i=1}x_i^2$最小就好了！

重新定义$dp[i][j]$为前i段路程分j天到达的每天路程平方的和的最小值

最后答案就应该是$dp[n][m]\times m-s[n^2]$

好，开始看状态转移

$dp[i][j]=min(dp[k][j-1]+(s[i]-s[k])^2)(j-1\leq k\leq i-1)$很简单的状态转移，但是复杂度$n^3$不接受，好像只有$n^2$可以的样子（带$log$的方法就别杠）

那怎么优化？

我们发现好像是跟$s[i]*s[k]$有关，不能直接单调队列，那斜率优化吧！

\[dp[i][j]=dp[k][j-1]+(s[i]-s[k])^2\\
dp[i][j]=dp[k][j-1]+s[i]^2+s[k]^2-2s[i]s[k]\\
dp[k][j-1]+s[k]^2=2s[i]s[k]-s[i]^2-dp[i][j]\\
\]

点为$(s[k],dp[k][j-1]+s[k]^2)$,斜率就是$2s[i]$

然后就是愉快的判断是撒子凸壳的时候了，刚学的

假设k1>k2，并且k1优于k2

\[dp[k1][j-1]+s[i]^2+s[k1]^2-2s[i]s[k1]<dp[k2][j-1]+s[i]^2+s[k2]^2-2s[i]s[k2]\\
dp[k1][j-1]+s[k1]^2-dp[k2][j-1]-s[k2]^2<2s[i](s[k1]-s[k2])\\
\frac {(dp[k1][j-1]+s[k1]^2)-(dp[k2][j-1]+s[k2]^2)}{(s[k1]-s[k2])}<2s[i]
\]

因为是小于，所以是下凸壳，然后就完了噢！

呼，公式真难打

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=3010;

int a[maxn];

ll f[maxn][maxn],s[maxn];

ll db(ll x){

	return x*x;

}

int n,m;

ll y(int j,int k){

	return f[k][j-1]+db(s[k]);

}

int q[maxn],head,tail=1;

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		s[i]=s[i-1]+a[i];

		f[i][1]=s[i]*s[i];

	}

	//以后最后都把第一种情况初始化了！！！！不然调用空的就容易错

	for(int j=2;j<=m;j++){//注意j为1也就是只分成一段的情况的初始化！！是s[i]*s[i]!!!!!!

		tail=head=0;

		q[tail++]=j-1;

		for(int i=j;i<=n;i++){

			while(head+1<tail&&y(j,q[head+1])-y(j,q[head])

			<=2*s[i]*(s[q[head+1]]-s[q[head]]))head++;

			if(head<tail){

				int k=q[head];

				f[i][j]=f[k][j-1]+db(s[i]-s[k]);

			}

			while(head+1<tail&&(y(j,q[tail-1])-y(j,q[tail-2]))*(s[i]-s[q[tail-1]])

			>=(y(j,i)-y(j,q[tail-1]))*(s[q[tail-1]]-s[q[tail-2]]))tail--;

			q[tail++]=i;

		}

	}

	printf("%lld",f[n][m]*m-db(s[n]));

	return 0;

}

「SDOI2016」征途题解的更多相关文章

「SDOI2016」征途
征途 Pine开始了从S地到T地的征途. 从S地到T地的路可以划分成$n$段,相邻两段路的分界点设有休息站. Pine计划用$m$天到达T地.除第$m$天外,每一天晚上Pine都必须在休息 ...
【LOJ】#2035. 「SDOI2016」征途
题解有人管它叫带权二分,有人管它叫dp凸优化,有人管它叫wqs二分-- 延伸出来还有zgl分治,xjp￥!%#[email protected]#￥!# 当我没说我们拆个式子,很容易发现所求的就是 \(m\sum_{i = 1 ...
loj2035 「SDOI2016」征途
学了斜率优化这题就能一气呵成地做出来啦qwqqwq #include <iostream> #include <cstdio> using namespace std; typ ...
[LOJ 2070] 「SDOI2016」平凡的骰子
[LOJ 2070] 「SDOI2016」平凡的骰子 [题目链接] 链接 [题解] 原题求的是球面面积可以理解为首先求多面体重心,然后算球面多边形的面积求重心需要将多面体进行四面体剖分,从而计算出 ...
liberOJ #2033. 「SDOI2016」生成魔咒后缀数组
#2033. 「SDOI2016」生成魔咒题目描述魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示.例如可以将魔咒字符 1 11.2 22 拼凑起来形成一个魔咒串 [1,2] [1, 2] ...
「SDOI2016」数字配对
「SDOI2016」数字配对题目大意传送门题解 $a_i$ 是 $a_j$ 的倍数,且 $\frac{a_i}{a_j}$ 是一个质数,则将 $a_i,a_j$ 质因数分解后,其 ...
「SDOI2016」储能表（数位dp）
「SDOI2016」储能表(数位dp) 神仙数位 $dp$ 系列可能我做题做得少 $QAQ$ $f[i][0/1][0/1][0/1]$ 表示第 $i$ 位 $n$ 是否到达上界 ...
题解 loj2065 「SDOI2016」模式字符串
点分治. 考虑经过当前分治中心$u$的点对数量. 这种数点对数的问题,有一个套路.我们可以依次考虑$u$的每个儿子,看用当前的儿子,能和之前已经考虑过的所有儿子,组成多少点对.这样所有合法的点 ...
【LOJ】#2070. 「SDOI2016」平凡的骰子
题解用了一堆迷之复杂的结论结果迷之好写的计算几何???? 好吧,要写立体几何了如果有名词不懂自己搜吧首先我们求重心,我们可以求带权重心,也就是x坐标的话是所有分割的小四面体的x坐标 * 四面体体 ...
【LOJ】#2069. 「SDOI2016」齿轮
题解我一开始还努力想这道题是不是有坑,被SDOI折磨到我觉得不能有那么水的题在-- 就是带权并查集维护一下两点间距离,如果新加一条边两个点在同一集合,看看已有的路径和新加的路径是否相等乘积可以在模 ...

随机推荐

Android studio debug模式获取变量的值
打断点.debug模式运行,Console界面旁边的Debugger界面,或者在变量上右键add to watches
JAVA线程池原理详解二
Executor框架的两级调度模型在HotSpot VM的模型中,JAVA线程被一对一映射为本地操作系统线程.JAVA线程启动时会创建一个本地操作系统线程,当JAVA线程终止时,对应的操作系统线程也 ...
解决IIS Express 80端口被占用的情况
VS2012运行站点的时候提示“无法启动IIS Express Web服务器,端口80正在使用” 于是CMD查看了一下端口使用情况,并且在任务管理器中查看相应的进程,但始终觉得不对,因为显示是Syst ...
大数据时代下的用户洞察：用户画像建立（ppt版）
大数据是物理世界在网络世界的映射,是一场人类空前的网络画像运动.网络世界与物理世界不是孤立的,网络世界是物理世界层次的反映.数据是无缝连接网络世界与物理世界的DNA.发现数据DNA.重组数据DNA是人 ...
C#: Create a WebRequest with HTTP Basic Authentication
http://blog.csdn.net/huangyaoshifog/article/details/4470675 myReq = WebRequest.Create(url); string u ...
jQuery的选择器中的通配符[id^='code'] 【转】
JQuery 1.选择器 (1)通配符: $("input[id^='code']");//id属性以code开始的所有input标签 $("input[id$='cod ...
C# 几十万级数据导出Excel，及Excel各种操作
先上导出代码 /// <summary> /// 导出速度最快 /// </summary> /// <param name="list">&l ...
在Mac OS上配置Android开发环境
1)安装配置NDK 1.1 下载NDK并解压缩下载路径 https://developer.android.com/tools/sdk/ndk/index.html 在terminal运行: chm ...
解题报告8VC Venture Cup 2017 - Elimination Round
题目链接:http://codeforces.com/contest/755 本蒟蒻做了半天只会做前两道题.. A. PolandBall and Hypothesis 题意:给出n,让你找出一个m, ...
javascript中onSubmit="return xxx()"的问题
javascript中onSubmit="return xxx()"刚开始我是想不通为什么要加return在里面呢,后来想想onSubmit="flase"就不 ...