自动搬运

查看原文

来自洛谷，原作者为

	Nostopathy 壶关条件 https://www.luogu.me/article/moj9ohqn#，壶关私|吾与吾爱皆亡于高塔，君与君心皆存于盛夏

搬运于2025-08-24 21:45:43，当前版本为作者最后更新于2025-08-20 10:14:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

本题的环很难处理，考虑破环成链，这里介绍一个函数：

std::rotate(iterator start, iterator middle, iterator end);

分别表示序列第一个元素，想要开始旋转的元素及序列最后一个元素。

在本题中，每次往后旋转一位进行 dp。定义 $dp_{i,j}$ 表示当前开 $i$ 道门，在第 $j$ 个房间的最小总距离。用一个变量 $s$ 记录 $j$ 以后的房间到 $j$ 的总路程，若用 $l$ 枚举以后的房间，则 $dp_{i,j} \leftarrow \min(dp_{i,j},dp_{i-1,l}+s)$。每次 dp 的最后答案为 $dp_{k,0}$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
#define rep(a, b, c, d) for(int a=b; a<=c; a+=d)
const int N = 1e2 + 5;
int n, K, r[N], dp[8][N];
void minn(int &q, int p) {
	q = min(q, p);
}
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> K;
	for(int i = 0; i < n; ++ i)
		cin >> r[i];
	int ans = 1145141919810364364;
	for(int i = 0; i < n; ++ i) { // 枚举环的开始
		memset(dp, 127, sizeof dp);
		dp[0][n] = 0; // 初始化
		for(int k = 1; k <= K; ++ k) // 枚举开门数
			for(int j = 0; j < n; ++ j) { // 枚举所在房间
				int s = 0;
				for(int l = j + 1; l <= n; ++ l) { // 枚举以后的房间
					s += r[l - 1] * (l - j - 1); // 计算距离
					minn(dp[k][j], dp[k - 1][l] + s); // 状态转移
				}
			}
		minn(ans, dp[K][0]); // 更新答案
		rotate(r, r + 1, r + n); // 后旋一位
	}
	cout << ans;
	return 0;
}

题解来之不易，麻烦留赞再走~

最后给个友链：P1299 切孔机，题号最小能发题解题目。