Day3 T3 跳跃机
移步原题
题目大意：
给定 n 个数，将它们分为 m 组，使得这 m 组数字之和的方差尽可能的小，设这个最小方差为 v ，请输出 v*m^2
数据范围：对于 100% 的数据，1≤n≤3000 且保证从起点到终点的总长度不超过 30000
原始做法：
因为注意到 n 并不是很大，故考虑对每组选取的数进行DP
我们先来推一波柿子
设这 m 组数的和分别为 a_1,a_2...a_m 他们的的平均数为 x
可列： $v=\frac{(x-a_1)^2+(x-a_2)^2+…+(x-a_m)^2}{m}$，
由 x=\frac{a_1+a_2+...+a_3}{m} 代入得：
$v=\frac{\frac{\sum\limits_{i=1}^{m}a_i}{m}-a_1)^2+(\frac{\sum\limits_{i=1}^{m}a_i}{m}-a_2)^2+…+(\frac{\sum\limits_{i=1}^{m}a_i}{m}-a_m)^2}{m}$，
化简得：
v=\frac{{a_1}^2+{a_2}^2+...+{a_m}^2}{m}- \frac{(\sum\limits_{i=1}^{m}a_i)^2}{m^2}
最后乘上 m^2 ：
v*m^2 = m X ({a_1}^2+{a_2}^2+...+{a_m}^2)- (\sum\limits_{i=1}^{m}a_i)^2
接下来就是愉快的推DP方程
用 f_{i,k} 表示将前 i 个数分为 k 组得到的最小的 和的平方之和（有点绕，即上述式中的 a_1^2+a_2^2+...+a_m^2 ） 再用一个 sum 数组预处理前 i 个数的和 接着枚举第 k-1 组的最后一个数，记为第 j 个数
能轻松得到方程式：
f_{i,k}=min(f_{i,k},f_{j,k-1}+(sum_i-sum_j)^2)
最终答案就是：
f_{n,m} X m - {sum_n}^2
复杂度为 O(n^2m) ，自信一发，哼哼……
90分……
注意到这坑比的数据范围，可没说 m 的大小啊 (ノ｀Д)ノ 最大的那个点直接 TLE ┭┮﹏┭┮
正解
考虑斜率优化，复杂度可降为 O(nm)
那么问题来了？什么是斜率优化？
接下来 我也不会讲的
不了解斜率优化的同学可以看看这篇博客学习一下，个人感觉这位博主解释的很清楚了blog by _ducati
现在，我们需要将我们的DP方程改为斜率式 y=kx+b ：
将 f_{i,k}=f_{j,k-1}+(sum_i-sum_j)^2
展开可得：$f_{i,k}=f_{j,k-1}+{sum_i}^2+{sum_j}^2-2$ X sum_i X sum_j ,
移项得：$f_{j,k-1}+{sum_i}^2+{sum_j}^2=2$ X sum_i X sum_j+f_{i,k}
                                            y                      =   k                  x          +        b
接下来就是直接套斜率优化的模板了
什么？想要代码？？请先关注天依谢谢喵
小结
其实能推出第一个DP方程就已经不错了，
斜率式的话靠感觉，把原方程展开，移移项也是能推出来的， 可能是玄学了点
得出斜率式就可以套模板了 还挺方便
私货
最后上代码
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long sum[3005],a[3005],q[3005],dp[3005][3005];
double x(long long a,long long b)
{
return dp[a][b-1]+sum[a]*sum[a];
}
double y(long long u,long long v,long long t)
{
return 1.000000*(x(u,t)-x(v,t))/(sum[u]-sum[v]);
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n-m+1;i++) dp[i][1]=sum[i]*sum[i];
for(int i=2;i<=m;i++)
{
int s=0,e=0;
for(int j=1;j<=n;j++)
{
while(s<e and 2*sum[j]>y(q[s],q[s+1],i)) s++;
long long p=q[s];
dp[j][i]=dp[p][i-1]+(sum[j]-sum[p])*(sum[j]-sum[p]);
while(e>s and y(q[e-1],q[e],i)>y(q[e-1],j,i)) e--;
q[++e]=j;
}
}
cout << dp[n][m]*m-sum[n]*sum[n];
return 0;
}