题目

点这里看题目。

分析

出题人已经开始拿高精作为考点了吗

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<i\le 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(n\log_2n)\) 的。

更进一步的，由于 \(s\) 也是不降的，因而我们可以使用单调队列维护决策点。这样就是 \(O(n)\) 了。

关于高精度，答案显然不会超过 \(1.6\times 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]] );

[CSP2019]划分

原文：https://www.cnblogs.com/crashed/p/13373778.html