题目
点这里看题目。
分析
出题人已经开始拿高精作为考点了吗
0pts ~ 24pts
数据太小，小到你甚至很难想到专门对付这些部分分的算法。
36pts
这应该是一个经典的问题， USACO 曾经考过类似的题目。
思想很简单，既然我们要求分出来的段单调递增，我们就把每一段的两个端点都放到状态里面。于是就有：
(f(i,j))：前 (j) 个数，最后一段的左端点为 (i) 的最小时间。
顺手设 (s_i=sum_{j=1}^i a_j) 。
转移显然：
时间复杂度 (O(n^3)) 。
64pts
对上面的 DP 进行优化。
考虑到 (i) 固定的时候，(j) 增大， (s_j-s_{i-1}) 也会增大，那么 (k) 最小值就会变小，并且 (j) 越大， (k) 越小。
因而我们可以确定 (i) ，单调枚举 (j) ，同时维护 (k) 的最小值和 (min{f(k,i-1)}) ，就可以做到均摊 (O(1)) 转移，总时间就降到了 (O(n^2)) 。
88pts ~ 100pts
首先我们需要一个很显然的不等式：
这就意味着，我们应该尽量让每一段的和变小。
那么，我们也可以知道，决策应该是单调的。更具体地说，我们设：
(f(i))：前 (i) 个数进行划分的最小结果。
对应有 (d(i)) ：前 (i) 个数进行划分，最后一段的划分点，即满足：
就应该有：(forall 1<ile n, d(i-1)le d(i))
考虑一个点如何能成为一个决策点。对于 (i, j(i<j))，如果 (i) 可以作为 (j) 的决策点，就意味着：
因而我们可以设 (g(i)=2s_i-s_{d(i)}) 。
下面我们又可以得到一个重要的性质：
感性理解就是，比你小，还比你强，你就退役了。
简单来说，由于 (g(i)>g(j)) ，则所有能用 (i) 进行决策的点，一定也可以用 (j) 决策。同时，根据贪心性质，从 (i) 划分得到的段比从 (j) 要大，因此不可能选择 $ i $ 作为决策点。
因此我们可以维护维护一个单调栈，保证内部的 (g) 是不降的。查询就可以在里面进行二分，这样是 (O(nlog_2n)) 的。
更进一步的，由于 (s) 也是不降的，因而我们可以使用单调队列维护决策点。这样就是 (O(n)) 了。
关于高精度，答案显然不会超过 (1.6 imes 10^{33}) 。因而，如果你懒了，你可以用 __int128 ，不然也可以用两个 long long 拼在一块，再不济就写个高精得了。
代码
64pts
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5005;
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
LL f[MAXN][MAXN];
LL s[MAXN];
for( int i = 1 ; i <= N ; i ++ ) f[1][i] = s[i] * s[i];
for( int i = 2 ; i <= N ; i ++ )
for( int j = 1 ; j <= N ; j ++ )
f[i][j] = INF;
LL mn; int l;
for( int i = 2 ; i <= N ; i ++ )
{
mn = INF, l = i;
for( int j = i ; j <= N ; j ++ )
{
while( l && s[i - 1] - s[l - 1] <= s[j] - s[i - 1] )
{
mn = MIN( mn, f[l][i - 1] );
l --;
}
f[i][j] = mn + ( s[j] - s[i - 1] ) * ( s[j] - s[i - 1] );
}
}
LL res = INF;
for( int i = 1 ; i <= N ; i ++ ) res = MIN( res, f[i][N] );
100pts
#define G( x ) ( 2ll * S[x] - S[dec[x]] )
typedef long long LL;
typedef __int128 LLL;
const LLL E = 1;
const int MAXN = 4e7 + 5, MAXM = 1e5 + 5;
int dec[MAXN], q[MAXN];
LL S[MAXN];
int h = 1, t = 0;
q[++ t] = 0;
for( int i = 1 ; i <= N ; i ++ )
{
while( h < t && G( q[h + 1] ) <= S[i] ) h ++;
dec[i] = q[h];
while( h < t && G( q[t] ) >= G( i ) ) t --;
q[++ t] = i;
}
LLL ans = 0;
for( int i = N ; i ; i = dec[i] )
ans = ans + E * ( S[i] - S[dec[i]] ) * ( S[i] - S[dec[i]] );