题解

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	deque<int> rooms(n);
	for (int &r : rooms) { cin >> r; }

	long long min_dist = INT64_MAX;
	for (int start_pos = 0; start_pos < n; start_pos++) {
		vector<vector<long long>> dp(k + 1,
		                             vector<long long>(n + 1, INT64_MAX));
		dp[0][n] = 0;
		for (int used_door = 1; used_door <= k; used_door++) {
			for (int i = 0; i < n; i++) {
				long long partial_dist = 0;
				for (int j = i + 1; j <= n; j++) {
					partial_dist += rooms[j - 1] * (j - i - 1);
					long long new_dist = dp[used_door - 1][j];
					if (new_dist < INT64_MAX) { new_dist += partial_dist; }
					dp[used_door][i] = min(dp[used_door][i], new_dist);
				}
			}
		}
		min_dist = min(min_dist, dp[k][0]);
		int first_room = rooms.front();
		rooms.pop_front();
		rooms.push_back(first_room);
	}

	cout << min_dist << endl;
}