题解 P4072 【[SDOI2016]征途】

· · 题解

打广告->这里

推式子（快哭了……）s^2*m^2=\sum _{i=1}^m (x_i-\bar{x})^2

s^2*m^2=m*\sum _{i=1}^m x_i^2-2*sum_n\sum _{i=1}^m x_i+sum_n^2 s^2*m^2=m*\sum _{i=1}^m x_i^2+(sum_n-\sum _{i=1}^m x_i)^2-(\sum _{i=1}^m x_i)^2

然后因为sum_n和\sum _{i=1}^m x_i两项是定值，且值相等，所以s^2*m^2=m*\sum _{i=1}^m x_i^2-(\sum _{i=1}^m x_i)^2

我们发现(\sum _{i=1}^m x_i)^2是一个定值，那么我们的目的就是让\sum _{i=1}^m x_i^2最小

总算扯到dp上了不容易啊……

我们设dp[i][l]表示前i条路l天走，最小的\sum _{a=1}^i x_a^2是多少，那么有如下的状态转移方程dp[i][l]=min\{dp[j][l-1]+(sum[i]-sum[j])^2\}

然后考虑斜率优化（以下省略l这一维）

假设j比k更优，则有dp[j]+(sum[i]-sum[j])^2<dp[k]+(sum[i]-sum[k])^2

展开，移项dp[j]+sum[j]^2-dp[k]-sum[k]^2<2*sum[i]*sum[j]-2*sum[i]*sum[k]

\frac{dp[j]+sum[j]^2-dp[k]-sum[k]^2}{sum[j]-sum[k]}<2*sum[i]

然后就可以上斜率优化了

ps:注意当l为0的时候dp要都初始化为sum[i]^2

//minamoto
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=3005;
ll sum[N],sp[N],dp[N];int n,m,h,t,q[N],r;
inline ll Y(int i){return sp[i]+sum[i]*sum[i];}
inline double slope(int j,int k){
    return (Y(j)-Y(k))*1.0/(sum[j]-sum[k]);
}
int main(){
    //freopen("testdata.in","r",stdin);
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    sum[i]=read()+sum[i-1],sp[i]=sum[i]*sum[i];
    for(int a=1;a<m;++a){
        h=t=0;q[0]=a;
        for(int i=a+1;i<=n;++i){
            while(h<t&&slope(q[h],q[h+1])<2*sum[i]) ++h;
            dp[i]=sp[q[h]]+(sum[i]-sum[q[h]])*(sum[i]-sum[q[h]]);
            while(h<t&&slope(q[t],q[t-1])>slope(q[t-1],i)) --t;q[++t]=i;
        }
        for(int i=1;i<=n;++i) sp[i]=dp[i];
    }
    printf("%lld\n",-sum[n]*sum[n]+m*dp[n]);
    return 0;
}