P4072 [SDOI2016]征途

// 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\n" , m * f[m & 1][n] - sqr(sum[n])) ;
    return 0 ;
}

P4072 [SDOI2016]征途

原文：https://www.cnblogs.com/Isaunoya/p/11656178.html