[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;}