自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 22:18:11，当前版本为作者最后更新于2021-12-09 13:40:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我用的是官方题解中提到的利用分治优化 $O(n^3 k)$ 的暴力程序的做法。优化后复杂度为 $O(n^2k \log n)$ 。

设 $f[i][j]$ 表示到了 $j-1$ 位置一共开了 $i$ 扇门。 $f[0][n]$ 初始化为 $0$ 。（有一维起点隐藏掉了） 。

$f[i][j] = \min { \{ f[i-1][k] + sum_{k,j}\} }$ ，其中 $k$ 是开门的位置。

直接跑显然是不行的，枚举起点、开门数、终点、开门点需要 $O(n^3 k)$ 的复杂度。

如果计算第 $i$ 个门在 $f[i][n/2]$ 中的位置，那么对于 $j<n/2$ 的 $f[i][j]$ 必须在其左侧，对于 $j>n/2$ 的 $f[i][j]$ 必须在其右侧。通过这种方式，我们可以在递归的每个级别平均将搜索空间减半。这样就将复杂度降了一个级别。也就是 $O(n^2k \log n)$ 。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005, K = 10;
#define INF 0x3fffffffffffffff
int t, n, k;
long long a[N], f[K][N], s[N][N];
inline int pos(int x, int y) {
  return x+y>=n?x+y-n:x+y;
}
inline long long calc(int a, int b) {
  return s[pos(a, t)][pos(b, n - a)];
}
inline void dfs(int k, int x1, int x2, int y1, int y2) {
	if (x1 == x2) return;
	int midx = (x1 + x2) >> 1;
	int midy = -1;
	f[k][midx] = INF;
	for (int j = max(midx + 1, y1); j < y2; j++) {
		long long v = f[k - 1][j] + calc(midx, j);
		if (v < f[k][midx]) {
			midy = j;
			f[k][midx] = v;
		}
	}
	dfs(k, x1, midx, y1, midy + 1);
	dfs(k, midx + 1, x2, midy, y2);
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for (int i = n - 1; ~i; i--)  cin >> a[i];
	for (int i = 0; i < n; i++) {
    	long long sum = 0;
		for (int j = 1; j <= n; j++) {
			s[i][j] = s[i][j - 1] + sum;
			sum += a[pos(i, j - 1)];
		}
	}
	memset(f, 63, sizeof(f));
	long long ans = INF;
	f[0][n] = 0;
	for (t = 0; t < n; t++) {
		for (int i = 1; i <= k; i++) dfs(i, 0, n, 1, n + 1);
		ans = min(ans, f[k][0]);
	}
	cout << ans << '\n';
	return 0;
}