征途题解

· · 题解

征途题解

恶心题。我太弱了

回到正题，

v^2=\frac{\sum_{i=1}^m(v_{i}-\bar{v})^2}{m} v^2*m^2=m*\sum_{i=1}^m(v_{i}-\bar{v})^2

将每个式子拆开：

m*(v_{i}-\bar{v})^2 m*({v_{i}}^2+{\bar{v}}^2-2*\frac{v_{i}*\sum_{k=1}^{m}v_{i}}{m}) m*({v_{i}}^2+({\frac{\sum_{k=1}^{m}v[k]}{m}})^2-2*\frac{v_{i}*\sum_{k=1}^{m}v_{i}}{m}) m*{v_{i}}^2+(\frac{\sum_{k=1}^{m}v[k]}{m})^2-2*v_{i}*\sum_{k=1}^{m}v_{i}

合起来，运用乘法分配律，即为：

v^2*m^2=m*\sum_{i=1}^{m}{v_{i}}^2+(\sum_{i=1}^{m}v_{i})^2-2*\sum_{i=1}^{m}v_{i}*\sum_{i=1}^{m}v_{i} v^2*m^2=m*\sum_{i=1}^{m}{v_{i}}^2-(\sum_{i=1}^{m}v_{i})^2

后面一项为常数,为路程总和,

便设f[k][i]为走了前i段路分配完前k天的最小平方和，设路程前缀和为sum，则：

暴力DP方程为:

f[k][i]=max f[k-1][j]+(sum[i]-sum[j])^2

拆平方项，移项：

f[k-1][j]+sum[j]^2=2*sum[i]*sum[j]+f[k][i]-sum[i]^2 \bullet y=f[k-1][j]+sum[j]^2 \bullet k=2*sum[i] \bullet x=sum[j] \bullet b=f[k][i]-sum[i]^2

维护一个单调的下凸壳即可,可以用循环队列节省空间。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3006;
int n,m,t,head,tail,o=0,sum[N],f[2][N];
struct point{int x,y;}tmp,q[N];
inline int read(){
   int T=0,F=1; char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
   while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
   return F*T;
}
bool check(point u,point v,int z){return v.y-u.y<=2*sum[z]*(v.x-u.x);}
bool check2(point u,point v,point z){return (v.y-u.y)*(z.x-v.x)>=(z.y-v.y)*(v.x-u.x);}
int main(){
    n=read(),m=read(),f[0][0]=0;
    for(int i=1;i<=n;++i) t=read(),sum[i]=sum[i-1]+t,f[o][i]=sum[i]*sum[i];
    for(int j=2;j<=m;++j){
        o^=1,q[1].x=0,q[1].y=0,head=tail=1;
        for(int i=1;i<=n;++i){
            while(head<tail&&check(q[head],q[head+1],i)) ++head;
            f[o][i]=q[head].y-2*sum[i]*q[head].x+sum[i]*sum[i],tmp.x=sum[i],tmp.y=f[o^1][i]+sum[i]*sum[i];
            while(head<tail&&check2(q[tail-1],q[tail],tmp)) --tail;
            q[++tail]=tmp;
        }
    }
    t=f[o][n]*m-sum[n]*sum[n];
    printf("%d\n",t);
    return 0;
}