4518: [Sdoi2016]征途

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 1861  Solved: 1034

[][][]

Description

Pine开始了从S地到T地的征途。

从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。

Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。

Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

帮助Pine求出最小方差是多少。

设方差是v，可以证明，v×m^2是一个整数。为了避免精度误差，输出结果时输出v×m^2。

Input

第一行两个数 n、m。

第二行 n 个数，表示 n 段路的长度

Output

 一个数，最小方差乘以 m^2 后的值

Sample Input

5 2

1 2 5 8 6

Sample Output

36

HINT

1≤n≤3000,保证从 S 到 T 的总路程不超过 30000

Source

[ ][ ][ ]

怎么感觉SD这套卷子大神们可以1h内随手AK啊，联赛难度的题目。

这题求$vm^2$绝对不是为了避免精度误差！是出题人为了掩藏裸的斜率优化DP的借口！

化一下式子就好了，下一维由上一维的单调队列得出，滚动即可。注意f[0]也要放进队列，化式子要谨慎一点。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 typedef long long ll; 6 using namespace std; 7  8 const ll N=100100,inf=1e18; 9 ll n,m,st,ed,a[N],s[N],q[N],f[N],g[N],ans;10 11 ll Y(ll x){ return f[x]+s[x]*s[x]; }12 13 int main(){14     freopen("journey.in","r",stdin);15     freopen("journey.out","w",stdout);16     scanf("%lld%lld",&n,&m); ans=inf;17     rep(i,1,n) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i],f[i]=s[i]*s[i];18     rep(i,2,m){19         st=0; ed=0;20         rep(j,0,n){21             while (st
        
         =(Y(j)-Y(q[ed]))*(2*(s[q[ed]]-s[q[ed-1]]))) ed--;24             q[++ed]=j;25         }26         ans=min(ans,g[n]); rep(j,0,n) f[j]=g[j];27     }28     printf("%lld\n",ans*m-s[n]*s[n]);29     return 0;30 }