征途
【问题描述】
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v，可以证明，v×m^2是一个整数。为了避免精度误差，输出结果时输出v×m^2。
【输入格式】
第一行两个数 n、m。
第二行 n 个数，表示 n 段路的长度
【输出格式】
一个数，最小方差乘以 m^2 后的
【样例输入】
5 2
1 2 5 8 6
1 2 5 8 6
【样例输出】
36
【数据范围】
1≤n≤3000,保证从 S 到 T 的总路程不超过 30000
题解：
来推一下式子：
方差：(x - aver) + (x - aver)+ ... + (x - aver) / m
然后题意要求乘m
那么
m×[(x - aver) + (x - aver)+ ... + (x - aver)]
= m×[x + x - 2aver(x+ x+ ... + x) + m × aver]
= m×(x + x) - 2sum+ sum(aver = sum / m)
= m×(x + x) - sum
其实m和sum都为常量，那么只要考虑中间的平方和部分
设f[i][j]为分到点j且分成i段时每一段的平方和
转移方程即为：f[i][j] = min(f[i][j], f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k])); (k < j)
三方效率肯定过不了，看出这是一个斜率优化的裸题，那就可以虾搞蛋了~\(≧▽≦)/~
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = ;
char c = getchar();
while('' > c || c > '') c = getchar();
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x;
}
int n, m;
int t, w;
int c[];
int s[];
long long aver;
long long f[][];
long long sum[];
double Up(int x, int y, int i)
{
return f[i - ][x] + sum[x] * sum[x] - f[i - ][y] - sum[y] * sum[y];
}
double Down(int x, int y)
{
return (sum[x] - sum[y]) << ;
}
long long Dp(int i, int j, int x)
{
return f[i - ][x] + (sum[j] - sum[x]) * (sum[j] - sum[x]);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i <= m; ++i)
for(int j = ; j <= n; ++j)
f[i][j] = 214748364721474836LL;
for(int i = ; i <= n; ++i)
{
scanf("%d", &c[i]);
sum[i] = sum[i - ] + c[i];
f[][i] = sum[i] * sum[i];
}
aver = sum[n];
for(int i = ; i <= m; ++i)
{
t = , w = ;
s[++w] = i - ;
for(int j = i; j <= n; ++j)
{
/*
for(int k = i - 1; k <= j; ++k)
f[i][j] = min(f[i][j], f[i - 1][k] + (sum[j] - sum[k]) * (sum[j] - sum[k]));
*/
while(t < w && Up(s[t], s[t + ], i) / Down(s[t], s[t + ]) <= sum[j]) ++t;
f[i][j] = Dp(i, j, s[t]);
while(t < w && Up(j, s[w], i) / Down(j, s[w]) <= Up(s[w], s[w - ], i) / Down(s[w], s[w - ])) --w;
s[++w] = j;
}
}
printf("%lld", (long long) m * f[m][n] - aver * aver);
}