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
36
1≤n≤3000,保证从 S 到 T 的总路程不超过 30000
鸣谢Menci上传
其实这题并不是很难,只怪自己太垃圾
首先我们把题目中给出的式子拆开
然后暴力推,发现最终答案只与v_i^2有关,v_i为拆出来的每个区间的长度
这样我们令f[i][j]表示前i个元素,选出了j段区间的最优方案
f[i][j]=min(f[i][j],\sum_{k=1}^{i-1} f[k][j-1])
然后暴力推推推,
最终可以化简为f[i][l]+2sum[i]sum[j]=f[j][l-1]+sum[j]^2
sum[i]为i的前缀和。
这样的话就可以愉快的斜率优化啦
第二维可以用滚动数组滚动掉
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cmath>
#include<algorithm>
#define int long long
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
using namespace std;
const int MAXN=1e5+10;
const int limit=100000;
int N,M;
int f[MAXN],g[MAXN];
int sum[MAXN];
int sqr(int x) {return x*x;}
int Query(int l,int r){return sum[r]-sum[l-1];}
int X(int x){return sum[x];}
int Y(int x){return g[x]+sqr(sum[x]);}
int slope(int x,int y){return (Y(y)-Y(x)) / (X(y)-X(x));}
int Q[MAXN];
main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
//freopen("b.out","w",stdout);
#endif
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
for(int i=1;i<=N;i++) g[i]=sqr(sum[i]);
for(int k=1;k<=M-1;k++)
{
memset(f,0x3f,sizeof(f));
int h=1,t=1;Q[1]=k-1;
for(int i=k+1;i<=N;i++)
{
while(h<t&&slope(Q[h],Q[h+1])<2*sum[i]) h++;
int j=Q[h];
f[i]=min(f[i],g[j]+sqr(Query(j+1,i)));
while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i)) t--;
Q[++t]=i;
}
memcpy(g,f,sizeof(f));
}
printf("%lld",-sum[N]*sum[N]+f[N]*M);
return 0;
}