P4072 [SDOI2016]征途

斜率优化裸题

题意大概是：求 最小的 (m^2s^2) =(m^2(frac{1}{m}sum_{i=1}^{m}(sum_i - {frac{sum_{i=1}^{m}sum_i}{m})^2}))

= (m^2 (frac{1}{m} sum_{i=1}^{m}sum_i^2 - frac{1}{m^2}(sum_{i=1}^{m}sum_i)^2))

= (msum_{i=1}^{m}sum_i ^2 - (sum_{i=1}^{m}sum_i)^2)

然后我们发现((sum_{i=1}^{m}sum_i)^2)是一个定值

所以我们只需要最小化(msum_{i=1}^{m}sum_i ^2)

发现 (m) 这个常数也可以最后再乘上

所以 考虑 最小化 (sum_{i=1}^{m}sum_i ^2)

转移方程是 (f_{i,j}) = (min){(f_{i-1,k}+(sum_j-sum_k)^2)}

这样就可以 (n^2m)求解了

考虑斜率优化

比较 (x) 和 (y)

设 (x) 的转移优于 (y)

即 (f_{i-1,x} +(sum_j-sum_x)^2<f_{i-1,y}+(sum_j-sum_y)^2)

(f_{i-1,x}+(sum_j^2+sum_x^2-2sum_{j}*sum_{x})<f_{i-1,y}+(sum_j^2+sum_y^2-2sum_j*sum_y))

(large frac{f_{i-1,x}-f_{i-1,y}+sum_x^2-sum_y^2}{sum_x-sum_y}<2*sum_{j})

很显然这样就可以斜率优化了

// Isaunoya
#include<bits/stdc++.h>
using namespace std ;
#define int long long
#define fi first
#define se second
#define pb push_back
inline int read() {
  register int x = 0 , f = 1 ;
  register char c = getchar() ;
  for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
  for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c & 15) ;
  return x * f ;
}
template < typename T > inline bool cmax(T & x , T y) {
	return x < y ? (x = y) , 1 : 0 ;
}
template < typename T > inline bool cmin(T & x , T y) {
	return x > y ? (x = y) , 1 : 0 ;
}
inline int QP(int x , int y , int Mod){ int ans = 1 ;
  for( ; y ; y >>= 1 , x = (x * x) % Mod)
    if(y & 1) ans = (ans * x) % Mod ;
  return ans ;
}
int n , m ;
const int N = 3000 + 5 ;
int a[N] , sum[N] ;
int f[2][N] , q[N] ;
inline int sqr(int x) { return x * x ; }
inline double slope(int i , int j , int k) {
  return 1.00 * (f[i & 1][j] - f[i & 1][k] + sqr(sum[j]) - sqr(sum[k])) / (double)(sum[j] - sum[k]) ;
}
signed main() {
  n = read() ; m = read() ;
  for(register int i = 1 ; i <= n ; i ++) a[i] = read() ;
  for(register int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + a[i] ;
  memset(f , 0x3f , sizeof(f)) ;
  f[0][0] = 0 ;
  for(register int i = 1 ; i <= n ; i ++) f[1][i] = sum[i] * sum[i] ;
  for(register int i = 2 ; i <= m ; i ++) {
    int h = 1 , t = 0 ;
    for(register int j = 1 ; j <= n ; j ++) {
      while(h < t && slope(i - 1 , q[h] , q[h + 1]) < 2 * sum[j]) h ++ ;
      int k = q[h] ; f[i & 1][j] = f[(i & 1) ^ 1][k] + sqr(sum[j] - sum[k]) ;
      while(h < t && slope(i - 1 , q[t] , q[t - 1]) > slope(i - 1 , q[t] , j)) t -- ;
      q[++ t] = j ;
    }
  } printf("%lld
" , m * f[m & 1][n] - sqr(sum[n])) ;
	return 0 ;
}