调了一个下午，我现在感觉自己要猝死了。 先讲一讲为什么这题要用斜率优化吧。 首先我们推一推： a n s = m 2 ∗ ( Σ ( a i − S / m ) 2 ) / m ans=m^2*(Σ(a_i - S/m)^2)/m ans=m2∗(Σ(ai−S/m)2)/m = m ∗ ( Σ a i 2 ) − S 2 =m*(Σa_i^2)-S^2 =m∗(Σai2)−S2 我们发现，要求出ans，只用求 Σ a i 2 Σa_i^2 Σai2。
我们设 d p [ j ] [ i ] dp[j][i] dp[j][i]为第j天走了前i条路。 可以写出dp式： d p [ j ] [ i ] = d p [ j − 1 ] [ k ] + ( p r e [ i ] − p r e [ k ] ) 2 ( k ∈ [ 1 , i − 1 ] ) dp[j][i]=dp[j-1][k]+(pre[i]-pre[k])^2(k∈[1,i-1]) dp[j][i]=dp[j−1][k]+(pre[i]−pre[k])2(k∈[1,i−1])
然后，我们就可以用斜率优化了。（不会斜率优化的自己去薅）
上马！
#include<cstdio> typedef long long ll; const int N = 3002; int n, m, head, tail, q[N]; ll a[N], pre[N], dp[N][N]; /*ll y(const int i, const int j, const int k) { return dp[k - 1][i] + pre[i] * pre[i] - dp[k - 1][j] - pre[j] * pre[j]; } ll x(const int i, const int j) { return 2 * (pre[i] - pre[j]); }*///上下两种打法都行 double slope(const int i, const int j, const int k) { return (double) (1.0 * (dp[k - 1][i] + pre[i] * pre[i] - dp[k - 1][j] - pre[j] * pre[j])) / (pre[i] - pre[j]); } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i ++) { scanf("%lld", &a[i]); pre[i] = pre[i - 1] + a[i]; dp[1][i] = pre[i] * pre[i]; } for(int j = 2; j <= m; j ++) { head = 1; tail = 0; for(int i = 1; i <= n; i ++) { while(head < tail && slope(q[head], q[head + 1], j) <= 2 * pre[i]) head ++;//为什么不用q[head] - 1? 路径j + i与j的路径差的平方 == 路径i dp[j][i] = dp[j - 1][q[head]] + (pre[i] - pre[q[head]]) * (pre[i] - pre[q[head]]); while(head < tail && slope(q[tail - 1], q[tail], j) >= slope(q[tail], i, j)) tail --; q[++ tail] = i; } } printf("%lld\n", m * dp[m][n] - pre[n] * pre[n]); return 0; }至于那个预处理嘛，没有什么为什么。
再注意，我们的循环要用j，i，不然就用不了优化了。
拜拜，我们下期再见！！！！！
