题目描述
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少
输入输出格式
输入格式：
第一行两个数 n、m。
第二行 n 个数，表示 n 段路的长度
输出格式：
一个数，最小方差乘以 m^2后的值
输入输出样例
输入样例#1：
5 2
1 2 5 8 6
输出样例#1：
36
说明
对于 100% 的数据 n≤3000
保证从 S 到 T 的总路程不超过 30000 。
斜率优化
我这题式子还化错了
求方差一脸懵逼==
首先根据方差的定义 (s^2 = sum_{i=1}^{m}{(x[i] - everagex)})
x[]表示每天走的路的长度
又因为题目要我们求方差乘上一个m^2
所以 (Ans = m^2 sum_{i=1}^{m}{x[i]-everagex}吗)
然后我们把式子化简一下
(Ans = msum{x[i]^2} - 2 m * everagex sum{x[i]} + m sum{everagex^2})
(Ans = msum{x[i]^2} - 2 * sum[n] * sum[n] + m * everagex sum{everagex})
$Ans = msum{x[i]^2} - 2 * sum[n]^2 + sum[n]^2 $
(Ans = msum{x[i]^2} - sum[n]^2)
然后就会发现第二项可以直接算出来
所以我们只需要考虑让(msum{x[i]^2})最小就可以了
这样是不是就可以DP了？
(f[i][j])表示第i天结束走完第j条路
DP式子也肥肠显然
(f[i][j] = f[i - 1][k] + (sum[j] - sum[k])^2)
然后再斜率优化一下
就一天一天的处理,所以可以消掉一维
(f[i])表示到第i条路的最小方差
(pre[i])表示前一天到第i条路得最小方差
(2 * sum[i] * sum[j] + f[i] = pre[j] + sum[i]^2 + sum[j]^2)
(k = 2 * sum[i])
(x= sum[j])
(y = pre[j] + sum[j]^2)
然后就是要注意预处理出只走一天的情况 (f[i] = sum[i]*sum[i])
#include<cstdio>
#include<cstring>
#include<algorithm>
# define int long long
const int M = 3005 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m ;
int p[M] , sum[M] , tot ;
int f[M] , pre[M] , q[M] , head , tail ;
inline double X(int i) { return sum[i] ; }
inline double Y(int i) { return pre[i] + sum[i] * sum[i] ; }
inline double Slope(int i , int j) { return (Y(i) - Y(j)) / (X(i) - X(j)) ;}
# undef int
int main() {
# define int long long
n = read() ; m = read() ;
for(int i = 1 ; i <= n ; i ++) {
p[i] = read() ;
sum[i] = sum[i - 1] + p[i] ;
pre[i] = sum[i] * sum[i] ;
}
for(int T = 1 ; T < m ; T ++) {
head = tail = 1 ;
for(int i = 1 ; i <= n ; i ++) {
while(head < tail && Slope(q[head] , q[head + 1]) < 2 * sum[i]) ++head ;
int j = q[head] ;
f[i] = pre[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) ;
while(head < tail && Slope(q[tail - 1] , q[tail]) > Slope(q[tail - 1] , i)) --tail ;
q[++tail] = i ;
}
for(int i = 1 ; i <= n ; i ++) pre[i] = f[i] ;
}
printf("%lld
",f[n] * m - sum[n] * sum[n]) ;
return 0 ;
}