[SDOI2016] 征途题解

P4072 [SDOI2016] 征途

题目描述

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

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

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

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

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

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

输入格式

第一行两个数n , m n, mn,m。

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

输出格式

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

输入输出样例 #1

输入 #1

5 2 1 2 5 8 6

输出 #1

36

说明/提示

数据范围及约定

• 对于30 % 30\%30%的数据，1 ≤ n ≤ 10 1 \le n \le 101≤n≤10；
• 对于60 % 60\%60%的数据，1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100；
• 对于100 % 100\%100%的数据，1 ≤ n ≤ 3000 1 \le n \le 30001≤n≤3000。

保证从S SS到T TT的总路程不超过3 × 1 0 4 3\times 10^43×104。

2 ≤ m ≤ n 2 \leq m \leq n2≤m≤n，每段路的长度为不超过3 × 1 0 4 3 \times 10^43×104的正整数。

思路

单调队列
斜率优化

代码见下

#include<bits/stdc++.h>usingnamespacestd;longlongn,m,a[3005],b[3005],f[3005][3005],op=0;intmain(){cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i];b[i]=b[i-1]+a[i];}memset(f,62,sizeof(f));for(inti=1;i<=n;i++){f[i][1]=b[i]*b[i];for(intj=2;j<=min((longlong)i,m);j++){f[i][j]=1e18+7;for(intk=max(0,i-100);k<=i-1;k++){f[i][j]=min(f[i][j],f[k][j-1]+(b[i]-b[k])*(b[i]-b[k]));}//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;}}cout<<f[n][m]*m-b[n]*b[n]<<endl;return0;}