自动搬运

查看原文

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:47:22，当前版本为作者最后更新于2023-05-16 21:25:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

看到题目，首先第一眼想到暴力。

最朴素的暴力方法肯定是先枚举长度 $i$，再枚举左右端点，最后计算差值，这样的复杂度是 $O(n^3)$ 的，肯定超时。

暴力代码：

#include <iostream>

using namespace std;
typedef long long ll;
#define int long long

int a[10101];

signed main(){
	int n;
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &a[i]);
	}
	for(int len = 1; len <= n; ++len){
		int l = 1, r = len;
		int cz = 1e15;
		while(r <= n){
			int L = l, R = r, nowcz = 0;
			while(L <= R){
				nowcz += abs(a[L] - a[R]);
				L++;
				R--;
			}
			++l;++r;
			cz = min(cz, nowcz);
		}
		printf("%lld ", cz);
	}
	return 0;
}

接下来就是本篇的重点：优化（当然我也不会和你说什么 dp 和双指针之类的）。

我们不妨举个例子：

初始时假设 $h = \{1,2,3,4,5,6,7\}$，我们先将长度为 $1$ 的算出来，很显然，都是 $0$，接下来不用着急算 $i = 2$ 的情况，算 $i = 3,5,7$ 的，我们会发现，在算其中的除了 $l$ 和 $r$ 端点外，其它的例如下标为 $4 \sim 4$ 的啊，$3 \sim 5$ 的都被之前给计算过了，于是我们大可开一个数组记录之前算过的差值，这样可以使得每次计算是 $O(1)$ 的复杂度。

由于奇偶性不同，$i$ 是偶数的情况也得分开记录差值。

复杂度是 $O(n^2)$ 的，超时不了，还是目前的最优解。

#include <iostream>

using namespace std;
typedef long long ll;

ll h[10101];
ll a[10101], b[10101];

int main(){
	int n;
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &h[i]);
	printf("0 ");
	for(int i = 2; i <= n; ++i){
		if(i % 2 == 1){
			int l = n-i+1, r = n;
			ll cz = 1e15;
			while(r >= i){
				a[r] = a[r-1] + abs(h[r] - h[l]);
				cz = min(cz, a[r]);
				--l;--r;
			}
			printf("%lld ", cz);
		}else{
			int l = n-i+1, r = n;
			ll cz = 1e15;
			while(r >= i){
				b[r] = b[r-1] + abs(h[r] - h[l]);
				cz = min(cz, b[r]);
				--l;--r;
			}
			printf("%lld ", cz);
		}
	}
	return 0;
}