自动搬运

查看原文

来自洛谷，原作者为

	_2022gdgzby01 小粉兔，粉又粉，两只耳朵拎起来，割完动脉割静脉，一动不动真可爱，扒了皮，剁了块，放在锅里炒个菜，加上水，盖上盖，出锅之前撒香菜，端个碗，拿双筷，张起嘴来尝一块，盐不咸，味不淡，真是美味下酒菜。

搬运于2025-08-24 22:26:30，当前版本为作者最后更新于2024-10-23 20:38:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$n$ 个数字，范围是 $1\sim s$，需要将 $1\sim s$ 分成 $k$ 段，使得每个数字必然只属于一段。分别计算每段的正序对，求和即为答案，现在需要让这个和最小，求最小值。

分析：

既然有 $k$ 段这个限制，那么采用 DP 的时候必然需要将 $k$ 作为一个状态：所以状态表示为 $dp_{i,j}$，以 $i$ 为分段的最后一个数字，一共 $j$ 段的答案。因为状态转移一定是 $dp_{i,j}\to dp_{k,j+1}$，所以将第二维优化。状态转移的时候，需要求一下在 $[i+1,j]$ 区间内的正序对个数，这个可以预处理解决：对于一个正序对 $x-y$，在二维坐标中将 $(x,y)$ 值加一。最后求得时候，其实就是要 $x$ 和 $y$ 均在给定的区间内的正序对个数，就是在一个正方形内的点的个数，预处理出每个点到原点的矩形中点的个数即可。