Solution
方差
=(frac{displaystylesum^{m}_{i=1}{{(x_i-ar{x})^2}}}{m})
=(displaystylesum^{m}_{i=1}{({x_i^2} + ar{x}^2 - 2*x_i*ar{x})})
=(displaystylesum^{m}_{i=1}{(x_i^2+frac{displaystylesum^{m}_{i=1}x_i}{m}- 2*x_i*frac{displaystylesum^{m}_{i=1}x_i}{m})})
=(displaystylesum^{m}_{i=1}{x_i^2}+displaystylesum^{m}_{i=1}x_i-frac{displaystylesum^{m}_{i=1}(2*x_i*displaystylesum^{m}_{i=1}x_i)}{m})
=(displaystylesum^{m}_{i=1}{x_i^2}+displaystylesum^{m}_{i=1}x_i-frac{displaystylesum^{m}_{i=1}x_i*displaystylesum^{m}_{i=1}(2*x_i)}{m})
=(displaystylesum^{m}_{i=1}{x_i^2}+displaystylesum^{m}_{i=1}x_i-frac{2*(displaystylesum^{m}_{i=1}x_i)^2}{m})
易得(displaystylesum^{m}_{i=1}x_i)和(displaystylesum^{m}_{i=1}x_i)是定值
所以只需要求(displaystylesum^{m}_{i=1}{x_i^2})的最小值就行了
然后再套上公式 注意得*上(m^2)
然后非常容易想到DP
定义
dp[i][j]表示前i个分成j份的平方和的最小值
易得状态转移方程
(color{pink}{dp[i][j] = min(dp[k][j-1]+(sum[i]-sum[k])^2);})
#include <cmath>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0;
char a;
while(!isdigit(a)) a = getchar();
while(isdigit(a)) x = (x << 3) + (x << 1) + a - '0',a = getchar();
return x;
}
const int MAXN = 3005;
const int inf = INT_MAX;
int x[MAXN],sum[MAXN],f[MAXN][MAXN];
inline int dmult(int x) {return x * x;}
int main()
{
int i,j,l,n = Read(1),m = Read(1);
memset(f,0x3f,sizeof(f));
for(i = 1;i <= n;i++)
{
x[i] = Read(1);
sum[i] += sum[i - 1] + x[i];
}
f[0][0] = 0;
for(i = 1;i <= n;i++)
{
for(l = 1;l <= min(i,m);l++)
{
for(j = 0;j < i;j++)
f[i][l] = min(f[i][l],f[j][l - 1] + dmult(sum[i] - sum[j]));
}
}
printf("%d",m * f[n][m] - dmult(sum[n]));
return 0;
}
算一下时间复杂度
(3000^3 >10^9)
显然不行
(color{pink}{TLE})
明显得优化下
看下标签 嗯 斜率优化
设(j>k)
当且仅当
(color{pink}{f[j][l - 1] + dmult(sum[i] - sum[j]) < f[k][l - 1] + dmult(sum[i] - sum[k])})
我们认为j比k优
否则 k更优
化简一下得到
(color{pink}{f[j][l-1]+sum[i]^2+sum[j]^2-2*sum[i]*sum[j]<f[k][l - 1] + sum[i]^2 + sum[k]^2-2*sum[i]*sum[k])})
(color{pink}{f[j][l-1]-f[k][l-1]+sum[j]^2-sum[k]^2<2*sum[i]*(sum[j]-sum[k])})
因为我们设了 (j>k)
所以(sum[j]-sum[k]>0)
所以
(color{pink}{frac{f[j][l-1]-f[k][l-1]+sum[j]^2-sum[k]^2}{(sum[j]-sum[k])}<2*sum[i]})
(color{pink}{frac{f[j][l-1]+sum[j]^2-f[k][l-1]-sum[k]^2}{(sum[j]-sum[k])}<2*sum[i]})
非常明显的斜率优化
P.S最后输出的时候按照我推出来的也行
#include <cmath>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
#define isdigit(x) ('0' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0;
char a;
while(!isdigit(a)) a = getchar();
while(isdigit(a)) x = (x << 3) + (x << 1) + a - '0',a = getchar();
return x;
}
const int MAXN = 3005;
const int inf = INT_MAX;
int x[MAXN],sum[MAXN],f[MAXN][MAXN],q[MAXN],g[MAXN];
inline int dmult(int x) {return x * x;}
inline double count_k(int u,int l,int r)
{
return (f[l][u] - f[r][u] + g[l] - g[r]) / (double)(sum[l] - sum[r]);
}
int main()
{
int i,j,l,n = Read(1),m = Read(1);
for(i = 1;i <= n;i++)
{
x[i] = Read(1);
sum[i] += sum[i - 1] + x[i];
g[i] = dmult(sum[i]);
}
int left,r;
for(i = 1;i <= n;i++) f[i][1] = dmult(sum[i]);
for(l = 2;l <= m;l++)
{
left = 1,r = 0;
for(i = 1;i <= n;i++)
{
while(left < r&&count_k(l - 1,q[left],q[left + 1]) < 2 * sum[i]) left++;
f[i][l] = f[q[left]][l - 1] + dmult(sum[i] - sum[q[left]]);
while(left < r&&count_k(l - 1,q[r - 1],q[r]) > count_k(l - 1,q[r],i)) r--;
q[++r] = i;
}
}
printf("%d",m * f[n][m] - dmult(sum[n]));
//按我推出的式子也行
return 0;
}